পাইথনে স্টক III কেনা এবং বিক্রি করার সেরা সময়

ধরুন আমাদের একটি অ্যারে আছে যার জন্য ith উপাদানটি i দিনে একটি প্রদত্ত স্টকের মূল্য উপস্থাপন করছে। সর্বাধিক লাভ খুঁজে পেতে আমাদের একটি অ্যালগরিদম তৈরি করতে হবে। আমরা সর্বাধিক দুটি লেনদেন সম্পূর্ণ করতে পারি। সুতরাং যদি প্রদত্ত মূল্য [3,3,5,0,1,3,1,4] হয়, তাহলে ফলাফল 6 হবে, যেমন আমরা 4 দিন (মূল্য 0) কিনব, তারপর 6 তম দিনে বিক্রি করব, ( মূল্য 3), তাই লাভ হল 3 – 0 =3৷ এখন কিন্তু 7 তম দিনে (দাম 1), এবং 8 তম দিনে বিক্রি করুন (মূল্য 4) তাই লাভ হল 4 – 1 =3৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s এর আকার, m :=t এর আকার। তাদের আগে ফাঁকা স্থান সংযুক্ত করে s এবং t আপডেট করুন

• আকারের একটি ম্যাট্রিক্স তৈরি করুন (n + 1) x (m + 1)

• dp[0, 0] :=1 সেট করুন, তারপর সমস্ত সারির 0 তম কলামের জন্য 1 সেট করুন, 1 রাখুন

• আমি 1 থেকে n

  রেঞ্জের মধ্যে

  • 1 থেকে m

    পরিসরে j এর জন্য

    • যদি s[i] =t[j], তাহলে

      • dp[i, j] :=dp[i – 1, j – 1]

    • dp[i, j] :=dp[i, j] + dp[i – 1, j]

• dp[n, m]

  ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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])
      xmin = [p[-1],n]
      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