用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