ধরুন আমাদের কাছে একটি কোম্পানির স্টক মূল্যের একটি তালিকা আছে কালানুক্রমিক ক্রমানুসারে, আমাদের খুঁজে বের করতে হবে যে আমরা স্টক ক্রয়-বিক্রয় থেকে সর্বোচ্চ কতটা লাভ করতে পারতাম। আমাদের অবশ্যই বিক্রি করার আগে কিনতে হবে, এবং আবার কেনার আগে স্টক বিক্রি করার পরে আমাদের অবশ্যই একদিন অপেক্ষা করতে হবে।
সুতরাং, ইনপুট যদি দামের মত হয় =[2, 6, 9, 4, 11], তাহলে আউটপুট হবে 11, যেমন আমরা 2-এ কিনতে পারি, তারপর 6-এ বিক্রি করতে পারি, একদিন অপেক্ষা করুন, তারপর 4-এ কিনুন এবং তারপর 11 এ বিক্রি করুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:
-
s :=0
-
b :=-ইনফিনিটি
-
আমি 0 থেকে দামের আকারের মধ্যে, কর
-
temp :=b
-
b :=সর্বোচ্চ b এবং (s - দাম[i])
-
যদি আমি অ-শূন্য হয়, তাহলে
-
s :=সর্বাধিক s এবং (temp + মূল্য[i - 1])
-
-
-
সর্বাধিক s এবং (b + দামের শেষ উপাদান) ফেরত দিন
আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:
উদাহরণ
class Solution: def solve(self, prices): s = 0 b = float("-inf") for i in range(len(prices)): temp = b b = max(b, s - prices[i]) if i: s = max(s, temp + prices[i - 1]) return max(s, b + prices[-1]) ob = Solution() prices = [2, 6, 9, 4, 11] print(ob.solve(prices))
ইনপুট
[2, 6, 9, 4, 11]
আউটপুট
11