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

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

  • j :=0 को इनिशियलाइज़ करने के लिए, जब j<=N, j को 1 से बढ़ाएँ -

    • dp[i, j, 1] :=- 1, dp[i, j, 0] :=- 1

• हल () नामक एक विधि को परिभाषित करें, यह गिरफ्तारी, i, n, k और स्थिति लेगा

• अगर मैं n के समान हूं, तो,

  • अगर स्थिति शून्य नहीं है, तो,

    • वापसी - 100000

  • वापसी 0

• अगर dp[i, k, status] -1 के बराबर नहीं है, तो,

  • वापसी डीपी [i, के, स्थिति]

• उत्तर:=हल करें (गिरफ्तारी, i + 1,n, k, स्थिति)

• अगर स्थिति शून्य नहीं है, तो,

  • उत्तर:=अधिकतम उत्तर, हल करें (arr,i + 1,n,k-1, स्थिति का व्युत्क्रम) + arr[i]

• अन्यथा -

  • अगर k>0, तो,

    • उत्तर:=अधिकतम उत्तर, हल (arr,i + 1,n,k, स्थिति स्थिति के विपरीत) - arr[i]

• वापसी डीपी [i, के, स्थिति]:=उत्तर

• मुख्य विधि से निम्न कार्य करें -

• फ़ंक्शन को कॉल करें प्री ()

• अगर k>=कीमतों का आकार /2, तो,

  • उत्तर:=0

  • आरंभ करने के लिए i :=1, जब i <कीमतों का आकार, i को 1 से बढ़ाएँ -

    • अगर कीमतें [i]> कीमतें [i-1], तो, उत्तर =उत्तर + कीमतें [i] - कीमतें [i - 1]

  • वापसी उत्तर

• रिटर्न सॉल्व (कीमतें, 0, कीमतों का आकार, 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}

आउटपुट

7