เวลาที่ดีที่สุดในการซื้อและขายหุ้น IV ใน C++

สมมติว่าเรามีอาร์เรย์ที่องค์ประกอบที่ 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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ 3 มิติของลำดับ N + 5 x N + 5 x 2

• กำหนดหนึ่งวิธีที่เรียกว่า pre()

• สำหรับการเริ่มต้น i :=0 เมื่อ i<=N เพิ่ม i โดย 1 ทำ −

  • สำหรับการเริ่มต้น j :=0 เมื่อ j<=N เพิ่ม j โดย 1 ทำ −

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

• กำหนดเมธอดหนึ่งวิธีที่เรียกว่า Solve() ซึ่งจะใช้ arr, i, n, k และสถานะ

• ถ้าฉันเหมือนกับ n แล้ว

  • หากสถานะไม่เป็นศูนย์

    • ผลตอบแทน - 100000

  • คืนค่า 0

• ถ้า dp[i, k, status] ไม่เท่ากับ -1 แล้ว

  • ส่งคืน dp[i, k, สถานะ]

• ตอบ :=แก้ (arr,i + 1,n,k,สถานะ)

• หากสถานะไม่เป็นศูนย์

  • ans :=สูงสุดของ ans, แก้(arr,i + 1,n,k - 1, ผกผันของสถานะ) + arr[i]

• มิฉะนั้น −

  • ถ้า k>0 แล้ว

    • ans :=max of ans,solve(arr,i + 1,n,k,inverse of status status) - arr[i]

• ส่งคืน dp[i, k, status] :=ans

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เรียกใช้ฟังก์ชัน pre()

• ถ้า k>=ขนาดของราคา /2 แล้ว

  • ตอบ :=0

  • สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของราคา ให้เพิ่ม i ขึ้น 1 ทำ −

    • ถ้าราคา[i]> ราคา[i-1] ดังนั้น ans =ans + ราคา[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