स्टॉक की कीमतों की सूची prices और प्रति बिक्री लेनदेन शुल्क fee दिया गया है। किसी भी संख्या में लेनदेन करके अधिकतम लाभ ढूंढें। खरीदने से पहले बेचना जरूरी है।
उदाहरण
इनपुट: prices = [2, 10, 4, 8], fee = 3
आउटपुट: 6
लेनदेन: 2 पर खरीदें, 10 पर बेचें (लाभ 5), 4 पर खरीदें, 8 पर बेचें (लाभ 1), कुल = 6।
एल्गोरिदम (पुनरावर्ती + मेमोइज़ेशन / DP)
दो अवस्थाएं: flag=0 (स्टॉक नहीं है, खरीद सकते हैं), flag=1 (स्टॉक है, बेच सकते हैं)।
recur(i, 0) = max(recur(i+1, 1) - prices[i], recur(i+1, 0))recur(i, 1) = max(recur(i+1, 1), recur(i+1, 0) + prices[i] - fee)- आधार मामला:
i == n→ 0 वापस करें।
पायथन कार्यान्वयन (पुनरावर्ती)
class Solution:
def solve(self, prices, fee):
n = len(prices)
from functools import lru_cache
@lru_cache(None)
def recur(i, holding):
if i == n:
return 0
if not holding:
# खरीदें या छोड़ें
return max(recur(i + 1, True) - prices[i], recur(i + 1, False))
else:
# बेचें या रखें
return max(recur(i + 1, True), recur(i + 1, False) + prices[i] - fee)
return recur(0, False)
# परीक्षण
ob = Solution()
print(ob.solve([2, 10, 4, 8], 3)) # 6
इटरेटिव DP (O(1) स्थान)
def solve_iterative(prices, fee):
cash = 0 # स्टॉक नहीं है
hold = -prices[0] # स्टॉक खरीदा हुआ
for price in prices[1:]:
cash = max(cash, hold + price - fee)
hold = max(hold, cash - price)
return cash
समय जटिलता
- पुनरावर्ती (मेमो के साथ): O(n) समय, O(n) स्थान।
- इटरेटिव: O(n) समय, O(1) स्थान।
