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 + 5x2の3D配列を1つ定義します

• pre（）と呼ばれる1つのメソッドを定義します

• iを初期化する場合：=0、i <=Nの場合、iを1つ増やしますdo-

  • j：=0を初期化する場合、j <=Nの場合、jを1増やしますdo −

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

• Solve（）と呼ばれる1つのメソッドを定義します。これには、arr、i、n、k、およびstatusが必要です

• iがnと同じ場合、

  • ステータスがゼロ以外の場合、

    • 戻り値-100000

  • 0を返す

• dp [i、k、status]が-1に等しくない場合、

  • dp [i、k、status]

    を返します

• ans：=resolve（arr、i + 1、n、k、status）

• ステータスがゼロ以外の場合、

  • ans：=ansの最大値、solve（arr、i + 1、n、k-1、ステータスの逆）+ arr [i]

• それ以外の場合-

  • k> 0の場合、

    • ans：=最大のans、solve（arr、i + 1、n、k、inverse of status status）-arr [i]

• dp [i、k、status]：=ans

  を返します

• メインの方法から、次のようにします-

• 関数pre（）

  を呼び出します

• k>=価格のサイズ/2の場合、

  • ans：=0

  • i：=1を初期化するために、i <価格のサイズの場合、iを1つ増やします-

    • 価格[i]>価格[i-1]の場合、ans =ans+価格[i]-価格[i-1]

  • ansを返す

• リターンソルブ（価格、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