स्टॉक खरीदने और बेचने का सबसे अच्छा समय


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग ByteDance सिस्को डीई शॉ ईबे Expedia Facebook गोल्डमैन सैक्स गूगल जेपी मॉर्गन माइक्रोसॉफ्ट मॉर्गन स्टेनली ओरेकल पेपैल Qualtrics सैमसंग VMware
ऐरे गतिशील प्रोग्रामिंग

समस्या का विवरण

समस्या "स्टॉक खरीदने और बेचने का सबसे अच्छा समय" बताता है कि आपको ए सरणी लंबाई 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 सरणी में तत्वों की संख्या है।

स्टॉक खरीदने और बेचने के लिए सर्वश्रेष्ठ समय के लिए इष्टतम दृष्टिकोण

एक बेहतर तरीका है एक फार्म सरणी जिसका ith तत्व अधिकतम मौजूद मान को संग्रहीत करता है कीमतों इंडेक्स I + 1 से n तक सरणी। यही है, हम भोले-भाले दृष्टिकोण में आंतरिक नेस्टेड लूप द्वारा किए गए काम को पूर्वनिर्मित कर रहे हैं। ताकि, हम सीधे अधिकतम प्राप्त करके आंतरिक नेस्टेड लूप को बदल सकें। Precomputation एल्गोरिथ्म निम्नलिखित तरीके से काम करता है।

  1. आकार की अधिकतम श्रृंखला नाम की एक सरणी बनाएं जिसका आकार बराबर हो कीमतों सरणी और एक चर अधिकतम और इसे न्यूनतम मान के रूप में प्रारंभ करें।
  2. में अंतिम सूचकांक से शुरू करें कीमतों सरणी।
    1. यदि कीमतें [i] अधिकतम से अधिक हैं
      1. अधिकतम मूल्य के रूप में अपडेट करें [i] और न्यूनतम मूल्य के रूप में अधिकतम [i] बनायें
    2. अगर कीमतें [i] अधिकतम से अधिक नहीं हैं
      1. अधिकतम अपडेट [i] = अधिकतम।
  3. पूर्व संगणना के बाद, हम भोले दृष्टिकोण का पालन करते हैं और आंतरिक नेस्टेड लूप को प्रतिस्थापित करते हैं जिसे हमने अधिकतम एमएसपी सरणी का उपयोग करके बनाया है।

छद्म कोड

// 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

जटिलता विश्लेषण

समय जटिलता

पर), जैसा कि हमने पूर्व लाभ और अधिकतम लाभ की गणना के दौरान, सरणी के n तत्वों पर पता लगाया है। समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

पर), क्योंकि प्रीकम्प्यूटेशन पार्ट के दौरान हम वर्तमान दिन के बाद एक दिन में अधिकतम विक्रय मूल्य जमा कर रहे थे। चूंकि यह सरणी में सभी तत्वों के लिए संग्रहीत है। अंतरिक्ष की जटिलता भी रैखिक है।
जहाँ n सरणी में तत्वों की संख्या है।