කොටස් මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ඩී ෂෝ ඊ බේ Expedia ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් ජේපී මෝගන් මයික්රොසොෆ්ට් මෝර්ගන් ස්ටැන්ලි ඔරකල් පේපෑල් ගුණාත්මකභාවය Samsung ජංගම දුරකථන VMware
අරා ගතික වැඩසටහන්කරණය

ගැටළු ප්රකාශය  

“කොටස් මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි අරාව දිග n හි මිල ගණන්, එහිදී ith මූලද්‍රව්‍යය ith දිනයේ තොගයේ මිල ගබඩා කරයි.
අපට එක් ගනුදෙනුවක් පමණක් කළ හැකි නම්, එනම්, එක් දිනක මිලදී ගැනීම සහ තවත් ඉදිරි දිනයක විකිණීම, උපයා ඇති උපරිම ලාභය කුමක් ද?

උදාහරණයක්  

prices[] = {7, 1, 5, 3, 6, 4}
5

ඇල්ගොරිතම  

අපි අයිත් දිනයේදී තොගය මිලට ගන්නේ නම්, උපරිම ලාභය උපයා ගන්නේ i + 1 සිට n අතර දිනකදී තොගය විකිණීමෙන් වන අතර, එමඟින් දවසේ තොගයේ උපරිම මිල ඇති අතර එය මිලට වඩා වැඩි වේ [i].
මිල ගණන් සලකා බලන්න = {7, 1, 5, 3, 6, 4}

කොටස් මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය
ඉතින්, උපරිම ලාභය උපයා ගන්නේ 2 වන දින තොගය මිලදී ගෙන 5 වන දින විකිණීමෙන්, උපයන උපරිම ලාභය 5 කි.

කොටස් මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය සඳහා බොළඳ ප්‍රවේශය  

ඉහත ඇල්ගොරිතම ක්‍රියාත්මක කිරීම සඳහා වන බොළඳ ප්‍රවේශය නම්, කූඩු ලූප දෙකක් ධාවනය කිරීමයි, එකක් මිලදී ගැනීමේ දිනය සඳහා සහ තවත් එකක් ඉදිරි දිනවල උපරිම ලාභය සොයා ගැනීම සඳහා ය.

මෙයද බලන්න
අරාවෙහි අනුපිටපත් සමඟ අනුපූරක පූර්ණ සංඛ්‍යාවක් තිබේදැයි පරීක්ෂා කරන්න

ව්‍යාජ කේතය

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (n ^ 2), මොකද අපි තොගය මිලදී ගැනීමට සහ විකිණීමට දවස තෝරා ගැනීම සඳහා කූඩු ලූප දෙකක් භාවිතා කරනවා. මේ අනුව කාල සංකීර්ණතාව බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), කිසිදු දත්ත ව්‍යුහයක එක් එක් මූලද්‍රව්‍යය පිළිබඳ කිසිදු තොරතුරක් අප විසින් ගබඩා නොකරන බැවින්. අපි භාවිතා කළේ නියත ඉඩක් පමණි. මේ අනුව අවකාශයේ සංකීර්ණතාව රේඛීය වේ.
මෙහි n යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

කොටස් මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය සඳහා ප්‍රශස්ත ප්‍රවේශය  

වඩා හොඳ ප්‍රවේශයක් වන්නේ අරාව එහි ඇති මූලද්‍රව්‍යයේ උපරිම අගය ගබඩා කරයි මිල i + 1 සිට n දක්වා දර්ශකය. එනම්, අප විසින් අභ්‍යන්තර කැදැලි ලූපය විසින් කරන ලද කාර්යයන් බොළඳ ප්‍රවේශයකින් පූර්ව ගණනය කිරීමකි. ඒ නිසා, අපට උපරිම කෙලින්ම සොයා ගැනීමෙන් අභ්‍යන්තර කැදැලි ලූපය ප්‍රතිස්ථාපනය කළ හැකිය. පූර්ව ගණනය කිරීමේ ඇල්ගොරිතම පහත පරිදි ක්‍රියා කරයි.

  1. ප්‍රමාණයට සමාන ප්‍රමාණයේ maxSP නමින් අරාවක් සාදන්න මිල අරාව සහ විචල්ය උපරිමය සහ එය අවම අගය ලෙස ආරම්භ කරන්න.
  2. හි අවසාන දර්ශකයෙන් ආරම්භ කරන්න මිල අරාව.
    1. මිල [i] උපරිමයට වඩා වැඩි නම්
      1. උපරිම මිල ලෙස යාවත්කාලීන කරන්න [i] සහ උපරිම අගය ලෙස උපරිම එස්පී [i] කරන්න
    2. මිල [i] උපරිමයට වඩා වැඩි නොවේ නම්
      1. යාවත්කාලීන කරන්න maxSP [i] = උපරිම.
  3. පූර්ව ගණනය කිරීමෙන් පසුව, අපි බොළඳ ප්‍රවේශය අනුගමනය කර අභ්‍යන්තර කැදැලි ලූපය ප්‍රතිස්ථාපනය කර අප විසින් නිර්මාණය කරන ලද මැක්ස්පී අරාව භාවිතා කරමු.
මෙයද බලන්න
අරාවෙහි බොහෝ නිරන්තර මූලද්‍රව්‍යය

ව්‍යාජ කේතය

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

කේතය

කොටස් ගැටළුව මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය සඳහා ජාවා කේතය

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}
5

කොටස් ගැටළුව මිලදී ගැනීමට සහ විකිණීමට හොඳම කාලය සඳහා සී ++ කේතය

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}
5

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), උපරිම ලාභය ගණනය කිරීම හා ගණනය කිරීමේදී අපි අරාවෙහි මූලද්‍රව්‍ය n හරහා ගමන් කර ඇති බැවින්. කාල සංකීර්ණතාව රේඛීය වේ.

මෙයද බලන්න
උපසිරැසි එකතුව ගැටළුව

අභ්‍යවකාශ සංකීර්ණතාව

මත), මක්නිසාද යත් පූර්ව ගණනය කිරීමේ කොටස තුළ අපි උපරිම විකුණුම් මිල වත්මන් දිනට පසු දිනක ගබඩා කර තැබූ බැවිනි. එය අරාවෙහි ඇති සියලුම මූලද්‍රව්‍ය සඳහා ගබඩා කර ඇති බැවින්. අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.
මෙහි n යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.