Գնման և վաճառքի լավագույն ժամանակը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg ByteDance Cisco ԴԵ Շոուն eBay Expedia facebook Goldman Sachs-ը Google JP Morgan Microsoft Morgan Stanley Պատգամախոս PayPal Քվեարկողներ Samsung VMware
Դասավորություն Դինամիկ ծրագրավորում

Խնդիրի հայտարարություն

«Բաժնետոմսեր գնելու և վաճառելու լավագույն ժամանակը» խնդիրը նշում է, որ ձեզ տրվում է անշարժ գույք դասավորություն n երկարության գների, որտեղ 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);
}

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n ^ 2), քանի որ մենք օգտագործում ենք երկու տեղադրված օղակ ՝ օրը հավաքելու համար բաժնետոմսերը գնելու և վաճառելու համար: Այսպիսով, ժամանակի բարդությունը բազմանդամ է:

Տիեզերական բարդություն

O (1), քանի որ մենք տվյալների որևէ կառուցվածքի յուրաքանչյուր տարրի վերաբերյալ որևէ տեղեկատվություն չենք պահում: Մենք օգտագործում ենք միայն անընդհատ տարածք: Այսպիսով, տարածության բարդությունը գծային է:
որտեղ n - զանգվածի տարրերի քանակը:

Բաժնետոմսեր գնելու և վաճառելու լավագույն ժամանակի օպտիմալ մոտեցում

Ավելի լավ մոտեցում է ձևավորել դասավորություն որի ith տարրը պահպանում է դրա մեջ առկա առավելագույն արժեքը գները զանգված i + 1 ցուցանիշից n: Այսինքն ՝ մենք նախահաշվարկում ենք միամիտ մոտեցմամբ ներքին բույնի օղակի կատարած աշխատանքը: Այսպիսով, մենք կարող ենք փոխարինել ներքին բույնի օղակը `ուղղակիորեն գտնելով առավելագույնը: Նախահաշվարկի ալգորիթմը գործում է հետևյալ եղանակով.

  1. Ստեղծեք զանգված `maxSP անվամբ, չափի հավասար է չափի գները զանգված և փոփոխական առավելագույնը և նախաձևակերպել այն որպես նվազագույն արժեք:
  2. Սկսեք վերջին ինդեքսից ներս գները զանգված
    1. Եթե ​​գները [i] ավելի մեծ են, քան առավելագույնը
      1. Թարմացրեք առավելագույնը որպես գներ [i] և առավելագույնը դարձրեք [i] ՝ որպես նվազագույն արժեք
    2. Այլապես, եթե գները [i] առավելագույնից բարձր չեն
      1. Թարմացնել maxSP [i] = առավելագույն:
  3. Նախնական հաշվարկից հետո մենք հետևում ենք միամիտ մոտեցմանը և փոխարինում ենք ներքին տեղադրված հանգույցին ՝ օգտագործելով մեր ստեղծած maxSP զանգվածը:

Կեղծ կոդ

// 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);
}

Կոդ

Java կոդ `ֆոնդային բորսա գնելու և վաճառելու լավագույն ժամանակի համար

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

C ++ կոդ `ֆոնդային բորսա գնելու և վաճառելու լավագույն ժամանակի համար

#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

Բարդության վերլուծություն

Timeամանակի բարդություն

Վրա), քանի որ մենք անցել ենք զանգվածի n տարրերի վրայով, առավելագույն շահույթի նախահաշվարկի և հաշվարկման ընթացքում: Timeամանակի բարդությունը գծային է:

Տիեզերական բարդություն

Վրա), քանի որ նախահաշվարկի մասի ընթացքում մենք պահում էինք վաճառքի առավելագույն գինը ընթացիկ օրվանից մեկ օրվա ընթացքում: Քանի որ այն պահվում է զանգվածի բոլոր տարրերի համար: Տիեզերական բարդությունը նույնպես գծային է:
որտեղ n - զանգվածի տարրերի քանակը: