用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做-

• dp [i，j，1]：=-1，dp [i，j，0]：=-1

• 对于初始化j：= 0，当j <= N时，将j增加1做-

• 定义一个称为Solve()的方法，它将采用arr，i，n，k和status

• 如果我与n相同，那么，

• 回报-100000

• 如果状态不为零，则

• 返回0

• 如果dp [i，k，status]不等于-1，则，

• 返回dp [i，k，状态]

• ans：= solve（arr，i + 1，n，k，status）

• 如果状态不为零，则

• ans：= ans的最大值，solve（arr，i + 1，n，k-1，状态的倒数）+ arr [i]

• 否则-

• ans：= ans，solve（arr，i + 1，n，k，状态逆的状态）的最大值-arr [i]

• 如果k> 0，

• 返回dp [i，k，status]：= ans

• 从主要方法中执行以下操作-

• 调用函数pre()

• 如果k> =价格的大小/ 2，那么，

• 如果价格[i]>价格[i-1]，则ans = ans +价格[i]-价格[i-1]

• 回答：= 0

• 用于初始化i：= 1，当i <价格大小时，将i加1做-

• 返回ans

• 返回求解（prices，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