Thời điểm tốt nhất để mua và bán cổ phiếu IV trong C ++

Giả sử chúng ta có một mảng mà phần tử thứ i là giá của một cổ phiếu nhất định cho ngày thứ i. Chúng tôi phải nghĩ ra một thuật toán để tìm ra lợi nhuận tối đa. Chúng tôi có thể hoàn thành nhiều nhất k giao dịch. Vì vậy, nếu đầu vào là [3,2,6,4,0,3] và k =2, thì đầu ra sẽ là 7, khi mua vào ngày 2 (khi giá =2) và bán vào ngày 3 (khi giá =6), lợi nhuận sẽ là 6-2 =4. Sau đó mua vào ngày 5 (giá là 0) và bán vào ngày 6 (giá là 3), lợi nhuận sẽ là 3-0 =3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng 3D có thứ tự N + 5 x N + 5 x 2

• Xác định một phương thức được gọi là pre ()

• để khởi tạo i:=0, khi i <=N, hãy tăng i lên 1 do -

  • để khởi tạo j:=0, khi j <=N, tăng j lên 1 do -

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

• Xác định một phương thức có tên là giải quyết (), phương thức này sẽ nhận arr, i, n, k và trạng thái

• nếu tôi giống với n, thì,

  • nếu trạng thái khác 0, thì

    • trở lại - 100000

  • trả về 0

• nếu dp [i, k, status] không bằng -1, thì

  • trả về dp [i, k, status]

• ans:=giải quyết (arr, i + 1, n, k, trạng thái)

• nếu trạng thái khác 0, thì

  • ans:=max của ans, giải quyết (arr, i + 1, n, k - 1, nghịch đảo trạng thái) + arr [i]

• Nếu không -

  • nếu k> 0 thì

    • ans:=max of ans, giải quyết (arr, i + 1, n, k, nghịch đảo trạng thái) - arr [i]

• trả về dp [i, k, status]:=ans

• Từ phương thức chính, hãy làm như sau -

• Gọi hàm pre ()

• nếu k> =kích thước của giá / 2, thì

  • ans:=0

  • để khởi tạo i:=1, khi i

    • nếu giá [i]> giá [i-1], thì ans =ans + giá [i] - giá [i - 1]

  • trả lại ans

• giải pháp trả về (giá, 0, kích thước của giá, k, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{ 3,2,6,4,0,3}

Đầu ra

7