C++ में स्टॉक खरीदने और बेचने का सर्वोत्तम समय IV

मान लीजिए हमारे पास एक सरणी है जिसके लिए i-वां तत्व दिन i के लिए दिए गए स्टॉक की कीमत है। हमें अधिकतम लाभ ढूंढने के लिए एक एल्गोरिदम तैयार करना है। हम अधिकतम k लेनदेन पूरे कर सकते हैं। तो यदि इनपुट [3,2,6,4,0,3] जैसा है और k = 2, तो आउटपुट 7 होगा, जैसे दिन 2 पर खरीदें (जब कीमत = 2) और दिन 3 पर बेचें (जब कीमत = 6), लाभ 6-2 = 4 होगा। फिर दिन 5 पर खरीदें (कीमत 0 है) और दिन 6 पर बेचें (कीमत 3 है), लाभ 3-0 = 3 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

क्रम N + 5 x N + 5 x 2 की एक 3D सरणी परिभाषित करें
एक विधि pre() परिभाषित करें
i := 0 से आरंभ करें, जब i<=N, i को 1 से बढ़ाएं करें -
- j := 0 से आरंभ करें, जब j<=N, j को 1 से बढ़ाएं करें -
  - dp[i, j, 1] := - 1, dp[i, j, 0] := - 1
एक विधि solve() परिभाषित करें, जो arr, i, n, k और status लेगी
यदि i, n के समान है, तो,
- यदि status शून्येतर है, तो,
  - - 100000 लौटाएं
- 0 लौटाएं
यदि dp[i, k, status] -1 के बराबर नहीं है, तो,
- dp[i, k, status] लौटाएं
ans := solve(arr,i + 1,n,k,status)
यदि status शून्येतर है, तो,
- ans := ans का अधिकतम, solve(arr,i + 1,n,k - 1, status का व्युत्क्रम) + arr[i]
अन्यथा -
- यदि k>0, तो,
  - ans := ans का अधिकतम,solve(arr,i + 1,n,k,status का व्युत्क्रम) - arr[i]
dp[i, k, status] := ans लौटाएं
मुख्य विधि से निम्नलिखित करें -
फ़ंक्शन pre() को कॉल करें
यदि k >= prices के आकार /2, तो,
- ans := 0
- i := 1 से आरंभ करें, जब i < prices का आकार, i को 1 से बढ़ाएं करें -
  - यदि prices[i] > prices[i-1], तो, ans = ans + prices[i] - prices[i - 1]
- ans लौटाएं
solve(prices,0, prices का आकार, k, 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}