ধরুন একটি অ্যারে আছে যার i-তম এলিমেন্ট i-তম দিনে একটি স্টকের দাম নির্দেশ করে। আমাদের সর্বোচ্চ প্রফিট বের করতে হবে। আমরা সর্বোচ্চ দুটি ট্রানজ্যাকশন সম্পন্ন করতে পারি। উদাহরণ: prices = [3,3,5,0,1,3,1,4] হলে রেজাল্ট ৬, কারণ ৪র্থ দিনে কিনে (দাম ০) ৬ষ্ঠ দিনে বিক্রি (দাম ৩) → প্রফিট ৩। আবার ৭ম দিনে কিনে (দাম ১) ৮ম দিনে বিক্রি (দাম ৪) → প্রফিট ৩।
সমাধানের ধাপগুলো −
- n := len(p); dp অ্যারে তৈরি করুন; ans = 0; xmin = p[0]
- i = 1 থেকে n-1 পর্যন্ত − xmin = min(xmin, p[i]); dp[i] = max(dp[i], p[i]-xmin); ans = max(ans, dp[i])
- xmax অ্যারে তৈরি করুন; xmax[-1] = p[-1]; tempp = 0
- i = n-2 থেকে 0 পর্যন্ত − xmax[i] = max(xmax[i+1], p[i])
- i = n-2 থেকে 0 পর্যন্ত − tempp = max(tempp, xmax[i+1]-p[i+1]); ans = max(ans, dp[i]+tempp)
- ans রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন −
class Solution(object):
def maxProfit(self, p):
if not p:
return 0
n = len(p)
dp = [0 for i in range(n)]
ans = 0
xmin = p[0]
for i in range(1,n):
xmin = min(xmin,p[i])
dp[i] = max(dp[i],p[i]-xmin)
ans = max(ans,dp[i])
xmax = [0 for i in range(n)]
xmax[-1] = p[-1]
tempp = 0
for i in range(n-2,-1,-1):
xmax[i] = max(xmax[i+1],p[i])
for i in range(n-2,-1,-1):
tempp = max(tempp,xmax[i+1]-p[i+1])
ans = max(ans,dp[i]+tempp)
return ans
ob = Solution()
print(ob.maxProfit([3,3,5,0,1,3,1,4]))
ইনপুট
[3,3,5,0,1,3,1,4]
আউটপুট
6
