Акцияны сатып алуу жана сатуу үчүн эң жакшы убакыт  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg ByteDance Cisco DE Shaw Окшош Expedia Facebook Goldman Sachs Гугл JP Morgan Microsoft Морган Стэнли Oracle PayPal Qualtrics Samsung VMware
согуштук тизме Динамикалык программалоо

Маселени билдирүү  

"Стокту сатып алуу жана сатуу үчүн эң жакшы убакыт" көйгөйүндө сизге ан согуштук тизме узундугу n баалар, бул жерде ith элемент акциялардын бааларын бир суткада сактайт.
Эгерде биз бир гана бүтүм жасай алсак, башкача айтканда, бир күнү сатып алып, башка бир күнү сатсак, анда максималдуу киреше кандай болот.

мисал  

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

Algorithm  

Эгерде биз акцияны бир күндө сатып алсак, анда максималдуу пайда 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);
}

Комплекстик анализ

Убакыт татаалдыгы

O (n ^ 2), Анткени, биз акцияларды сатып алуу жана сатуу үчүн, эки уя курулган циклин колдонуп жатабыз. Ошентип убакыттын татаалдыгы poltnomial болуп саналат.

Космостун татаалдыгы

O (1), анткени биз эч кандай маалымат структурасында ар бир элемент жөнүндө эч кандай маалымат сактабайбыз. Биз туруктуу мейкиндикти гана колдонуп келе жатабыз. Ошентип космос татаалдыгы сызыктуу болот.
мында n - массивдеги элементтердин саны.

Акцияны сатып алуу жана сатуу үчүн ыңгайлуу убакыт  

Жакшыраак ыкма - бул согуштук тизме анын элементинде бар максималдуу мааниси сакталат баалар массив i + 1ден nге чейин. Башкача айтканда, биз ички уюлдук жасаган ишти алдын-ала эсептеп жатабыз. Ошентип, биз максимумду түздөн-түз таап, ички уяланган циклди алмаштыра алабыз. Эсептөө алгоритми төмөнкүдөй иштейт.

  1. MaxSP деген массивди түзүп, көлөмүнө барабар баалар массив жана өзгөрүлмө max жана аны минималдуу маани катары баштаңыз.
  2. Акыркы индекстен баштаңыз баалар массив.
    1. Эгерде баалар [i] максимумдан жогору болсо
      1. Max бааларын [i] катары жаңыртып, maxSP [i] минималдык мааниси катары жасаңыз
    2. Эгерде баалар [i] максимумдан жогору болбосо, анда башка
      1. MaxSP [i] = max жаңыртуу.
  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

Комплекстик анализ

Убакыт татаалдыгы

O (n), массивдин n элементин басып өткөндөй, максималдуу кирешени эсептөө жана эсептөө учурунда. Убакыттын татаалдыгы сызыктуу.

ошондой эле
Ички топтом көйгөйү

Космостун татаалдыгы

O (n), анткени эсептөө учурунда биз сатуу максималдуу баасын учурдагы күндөн кийинки бир күндө сактадык. Ал массивдеги бардык элементтер үчүн сакталгандыктан. Космостун татаалдыгы дагы сызыктуу.
мында n - массивдеги элементтердин саны.