ყიდვისა და გაყიდვის საუკეთესო დრო


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg ByteDance Cisco დე შოუ eBay Expedia Facebook Goldman Sachs Google JP Morgan microsoft Morgan Stanley Oracle PayPal Qualtrics 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 არის მასივის ელემენტების რაოდენობა.

ოპტიმალური მიდგომა საფონდო ყიდვისა და გაყიდვის საუკეთესო დროისთვის

უკეთესი მიდგომაა ფორმირება მასივი რომლის ith ელემენტი ინახავს მაქსიმალურ მნიშვნელობას ფასები მასივი i + 1-დან n- მდე. ეს არის ის, რომ ჩვენ წინასწარ ვთვლით შინაგან წყობილი მარყუჟის მიერ შესრულებულ სამუშაოს გულუბრყვილო მიდგომაში. ასე რომ, ჩვენ შეგვიძლია ჩავანაცვლოთ შიდა წყობილი მარყუჟი, პირდაპირ ვიპოვნოთ მაქსიმუმი. წინასწარი გამოთვლის ალგორითმი მუშაობს შემდეგნაირად.

  1. შექმნა მასივი, სახელად maxSP ზომა უდრის ზომის ფასები მასივი და ცვლადი მაქს და ინიცირება მას მინიმალურ მნიშვნელობად.
  2. დაიწყეთ ბოლო ინდექსში ფასები მასივი
    1. თუ ფასები [i] - ზე მეტია
      1. განაახლეთ max როგორც ფასები [i] და გააკეთეთ maxSP [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);
}

კოდი

ჯავის კოდი საუკეთესო დროის ყიდვისა და გაყიდვის საფონდო პრობლემისთვის

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 არის მასივის ელემენტების რაოდენობა.