Акцияны сатып алу және сатудың ең жақсы уақыты


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Cisco DE Шоу еВау Expedia Facebook Голдман Сакс Google JP Morgan Microsoft Морган Стэнли Oracle PayPal Квалификация Samsung VMware
Array Динамикалық бағдарламалау

Проблемалық мәлімдеме

«Акцияларды сатып алу-сатудың ең жақсы уақыты» проблемасында сізге берілген массив 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);
}

Күрделілікті талдау

Уақыттың күрделілігі

O (n ^ 2), өйткені біз акцияны сатып алу-сату үшін екі ұялы циклды қолданамыз. Осылайша уақыттың күрделілігі полтномиальды болады.

Ғарыштың күрделілігі

O (1), өйткені біз кез-келген деректер құрылымында әр элементке қатысты ешқандай ақпарат сақтамаймыз. Біз тек тұрақты кеңістікті қолдандық. Осылайша кеңістіктің күрделілігі сызықтық болып табылады.
Мұндағы n - массивтегі элементтер саны.

Акцияны сатып алу және сату үшін оңтайлы тәсіл

Жақсы тәсіл - қалыптастыру массив оның элементінде болатын максималды мән сақталады бағасы массив i + 1 индексінен n-ге дейін. Яғни, біз ішкі ұяшықпен жасалған жұмысты аңғалдық тәсілмен алдын ала есептеп жатырмыз. Осылайша, ішкі максималды тікелей максимумды табу арқылы ауыстыра аламыз. Алдын ала есептеу алгоритмі келесі тәртіпте жұмыс істейді.

  1. MaxSP өлшемді массив деп өлшемге тең массив жасаңыз бағасы массив және айнымалы және оны минималды мән ретінде инициализациялайды.
  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 - массивтегі элементтер саны.