पायथन में कूलडाउन के साथ स्टॉक खरीद-बिक्री से अधिकतम लाभ का प्रोग्राम

स्टॉक की कीमतों की सूची prices दी गई है। अधिकतम लाभ ढूंढें जहां आप खरीदने से पहले बेच नहीं सकते, और बेचने के बाद अगले दिन खरीद नहीं सकते (1 दिन का कूलडाउन)।

उदाहरण

इनपुट: prices = [2, 6, 9, 4, 11]

आउटपुट: 11

लेनदेन: 2 पर खरीदें, 6 पर बेचें (लाभ 4), दिन 2 कूलडाउन, 4 पर खरीदें, 11 पर बेचें (लाभ 7), कुल = 11।

एल्गोरिदम (स्टेट मशीन DP)

दो अवस्था चर बनाए रखें:

s (sold/कैश): स्टॉक नहीं है, खरीद सकते हैं।
b (buy/होल्ड): स्टॉक है, बेच सकते हैं।

प्रत्येक दिन price के लिए:


temp = b
b = max(b, s - price)      # खरीदें या रखें
if i > 0:
    s = max(s, temp + prices[i-1])  # बेचें या रखें (कूलडाउन के कारण i-1)

अंत में max(s, b + prices[-1]) वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, prices):
        s = 0
        b = float("-inf")
        for i, price in enumerate(prices):
            temp = b
            b = max(b, s - price)
            if i:
                s = max(s, temp + prices[i - 1])
        return max(s, b + prices[-1])

# परीक्षण
ob = Solution()
print(ob.solve([2, 6, 9, 4, 11]))  # 11
print(ob.solve([1, 2, 3, 0, 2]))   # 3

स्पष्टीकरण

b = स्टॉक रखने पर अधिकतम लाभ (खरीदने के बाद)।
s = स्टॉक न रखने पर अधिकतम लाभ (बेचने के बाद, कूलडाउन समाप्त)।
बेचते समय prices[i-1] का उपयोग कूलडाउन को लागू करता है: आज बेचा → कल नहीं खरीद सकते।

समय जटिलता

O(n) समय, O(1) स्थान।
सामान्य DP (3 अवस्थाएं: होल्ड, कूलडाउन, फ्री) का अनुकूलित संस्करण।