Καλύτερος χρόνος για αγορά και πώληση μετοχών


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg ByteDance Cisco DE Shaw eBay Expedia Facebook Goldman Sachs Google JP Morgan Microsoft Morgan Stanley μαντείο PayPal Qualtrics Samsung VMware
Παράταξη Δυναμικός προγραμματισμός

Δήλωση προβλήματος

Το πρόβλημα "Best Time to Buy and Sell Stock" δηλώνει ότι σας δίνεται ένα παράταξη των τιμών μήκους n, όπου το στοιχείο ith αποθηκεύει την τιμή του αποθέματος την ith ημέρα.
Εάν μπορούμε να κάνουμε μόνο μία συναλλαγή, δηλαδή να αγοράσουμε μια μέρα και να πουλήσουμε σε μια άλλη επερχόμενη ημέρα, ποιο θα είναι το μέγιστο κέρδος που κερδίζεται.

Παράδειγμα

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

Αλγόριθμος

Εάν αγοράσουμε το απόθεμα την ith ημέρα, το μέγιστο κέρδος κερδίζεται από την πώληση του αποθέματος σε μια ημέρα μεταξύ i + 1 έως n, έτσι ώστε η ημέρα να έχει τη μέγιστη τιμή του αποθέματος και ότι είναι μεγαλύτερη από την τιμή [i].
Εξετάστε τις τιμές = {7, 1, 5, 3, 6, 4}

Καλύτερος χρόνος για αγορά και πώληση μετοχών
Έτσι, το μέγιστο κέρδος κερδίζεται αγοράζοντας το απόθεμα την ημέρα 2 και το πουλώντας την ημέρα 5, το μέγιστο κέρδος που κερδίζετε είναι 5.

Naive προσέγγιση για τον καλύτερο χρόνο αγοράς και πώλησης αποθεμάτων

Η αφελής προσέγγιση για την εφαρμογή του παραπάνω αλγορίθμου είναι η εκτέλεση δύο ένθετων βρόχων, ένας για την ημέρα αγοράς και ένας άλλος για την εύρεση του μέγιστου κέρδους τις προσεχείς ημέρες.

Ψευδοκώδικας

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), γιατί χρησιμοποιούμε δύο ένθετους βρόχους για την παραλαβή της ημέρας για αγορά και πώληση του αποθέματος. Έτσι η πολυπλοκότητα του χρόνου είναι πολυωνυμική.

Διαστημική πολυπλοκότητα

Ο (1), δεδομένου ότι δεν έχουμε καμία πληροφορία σχετικά με κάθε στοιχείο σε οποιαδήποτε δομή δεδομένων. Χρησιμοποιούμε μόνο σταθερό χώρο. Έτσι, η πολυπλοκότητα του χώρου είναι γραμμική.
όπου n είναι ο αριθμός των στοιχείων στον πίνακα.

Βέλτιστη προσέγγιση για τον καλύτερο χρόνο αγοράς και πώλησης αποθεμάτων

Μια καλύτερη προσέγγιση είναι να σχηματίσετε ένα παράταξη του οποίου το στοιχείο αποθηκεύει τη μέγιστη τιμή που υπάρχει στο τιμές πίνακας από το ευρετήριο i + 1 έως n. Δηλαδή, υπολογίζουμε την εργασία που έγινε από τον εσωτερικό ένθετο βρόχο σε αφελής προσέγγιση. Έτσι, μπορούμε να αντικαταστήσουμε τον εσωτερικό ένθετο βρόχο βρίσκοντας απευθείας το μέγιστο. Ο αλγόριθμος υπολογισμού λειτουργεί με τον ακόλουθο τρόπο.

  1. Δημιουργήστε έναν πίνακα με το όνομα maxSP του μεγέθους ισούται με το μέγεθος του τιμές πίνακα και μια μεταβλητή max και αρχικοποιήστε την ως την ελάχιστη τιμή.
  2. Ξεκινήστε από το τελευταίο ευρετήριο το τιμές πίνακας.
    1. Εάν οι τιμές [i] είναι μεγαλύτερες από το μέγ
      1. Ενημερώστε το μέγιστο ως τιμές [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);
}

Κώδικας

Κώδικας 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Επί), καθώς έχουμε διασχίσει n στοιχεία του πίνακα, κατά τον υπολογισμό και τον υπολογισμό του μέγιστου κέρδους. Η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

Επί), γιατί κατά τη διάρκεια του τμήματος υπολογισμού αποθηκεύσαμε τη μέγιστη τιμή πώλησης μια ημέρα μετά την τρέχουσα ημέρα. Δεδομένου ότι αποθηκεύεται για όλα τα στοιχεία του πίνακα. Η πολυπλοκότητα του διαστήματος είναι επίσης γραμμική.
όπου n είναι ο αριθμός των στοιχείων στον πίνακα.