C++ এ স্টক IV কেনা এবং বিক্রি করার সেরা সময়

ধরুন আমাদের একটি অ্যারে আছে যার জন্য i-th উপাদানটি হল দিনের i জন্য একটি প্রদত্ত স্টকের মূল্য। সর্বাধিক লাভ খুঁজে পেতে আমাদের একটি অ্যালগরিদম তৈরি করতে হবে। আমরা সর্বাধিক k লেনদেন সম্পূর্ণ করতে পারি। সুতরাং ইনপুট যদি [3,2,6,4,0,3] এবং k =2 এর মত হয়, তাহলে আউটপুট হবে 7, যেমন ২য় দিনে কিনবে (যখন দাম =2) এবং ৩য় দিনে বিক্রি করবে (যখন দাম) =6), লাভ হবে 6-2 =4। তারপর 5 দিন কিনুন (মূল্য 0) এবং 6 তম দিনে বিক্রি করুন (দাম 3), লাভ হবে 3-0 =3।

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

N + 5 x N + 5 x 2
অর্ডারের একটি 3D অ্যারে সংজ্ঞায়িত করুন
প্রি()
নামে একটি পদ্ধতি সংজ্ঞায়িত করুন
শুরু করার জন্য i :=0, যখন i<=N, i 1 do −
দ্বারা বাড়ান
- j শুরু করার জন্য :=0, যখন j<=N, j বাড়ান 1 do −
  - dp[i, j, 1] :=- 1, dp[i, j, 0] :=- 1
সমাধান() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি arr, i, n, k এবং স্থিতি
লাগবে
যদি আমি n এর মত হয়, তাহলে,
- যদি স্ট্যাটাস অ-শূন্য হয়, তাহলে,
  - ফেরত - 100000
- রিটার্ন 0
যদি dp[i, k, status] -1 এর সমান না হয়, তাহলে,
- dp[i, k, স্থিতি]
  ফেরত দিন
উত্তর :=সমাধান (arr,i + 1,n,k,status)
যদি স্ট্যাটাস অ-শূন্য হয়, তাহলে,
- ans :=উত্তরের সর্বোচ্চ, সমাধান (arr,i + 1,n,k - 1, অবস্থার বিপরীত) + arr[i]
অন্যথা -
- যদি k>0, তাহলে,
  - ans :=উত্তরের সর্বোচ্চ, সমাধান (arr,i + 1,n,k, স্থিতি স্থিতির বিপরীত) - arr[i]
রিটার্ন dp[i, k, status] :=ans
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
প্রি()
ফাংশনটিকে কল করুন
যদি k>=দামের আকার /2, তাহলে,
- উত্তর :=0
- শুরু করার জন্য i :=1, যখন i <দামের আকার, i 1 ডু −
  বাড়াবে
  - যদি দাম[i]> দাম[i-1], তাহলে, ans =ans + দাম[i] - দাম[i - 1]
- উত্তর ফেরত দিন
রিটার্ন সলভ (দাম,0, দামের আকার, কে, 0)

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N + 5][N + 5][2];
class Solution {
   public:
   void pre(){
      for(lli i =0;i<=N;i++){
         for(lli j = 0;j<=N;j++){
            dp[i][j][1]=-1;
            dp[i][j][0]=-1;
         }
      }
   }
   lli solve(vector<int> &arr, lli i,lli n,lli k, lli status){
      if(i == n){
         if(status)return -100000;
         return 0;
      }
      if(dp[i][k][status]!=-1)return dp[i][k][status];
      lli ans = solve(arr, i+1,n,k,status);
      if(status){
         ans = max(ans,solve(arr,i+1,n,k-1,!status)+ arr[i]) ;
      } else {
         if(k>0){
            ans = max(ans,(lli)solve(arr,i+1,n,k,!status)- arr[i]) ;
         }
      }
      return dp[i][k][status] = ans;
   }
   int maxProfit(int k, vector<int>& prices) {
      pre();
      if(k>=prices.size()/2){
         int ans = 0;
         for(int i = 1; i < prices.size(); i++){
            if(prices[i] > prices[i-1])ans += prices[i] - prices[i-1];
         }
         return ans;
      }
      return solve(prices,0,prices.size(),k,0);
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,6,4,0,3};
   cout << (ob.maxProfit(2, v));
}

ইনপুট

{ 3,2,6,4,0,3}