Mua bán cổ phiếu IV (Best Time to Buy and Sell Stock IV) trong C++

Cho mảng giá cổ phiếu prices, tối đa k giao dịch (mua rồi bán = 1 giao dịch). Tối đa hóa lợi nhuận.

Ví dụ

prices = [3,2,6,4,0,3], k = 2

Mua ngày 2 (giá 2), bán ngày 3 (giá 6) → lãi 4.

Mua ngày 5 (giá 0), bán ngày 6 (giá 3) → lãi 3.

Tổng = 7.

Thuật toán: DP 3 chiều + Tối ưu

Trạng thái: dp[i][k][hold] = lợi nhuận tối đa tại ngày i, còn k giao dịch, trạng thái hold (0=không có cổ phiếu, 1=đang nắm).

Chuyển trạng thái:

• Nghỉ: dp[i][k][hold] = dp[i+1][k][hold]
• Mua (hold=0, k>0): dp[i][k][0] = max(..., -prices[i] + dp[i+1][k][1])
• Bán (hold=1): dp[i][k][1] = max(..., prices[i] + dp[i+1][k-1][0])

Tối ưu quan trọng

Nếu = n/2 → không giới hạn giao dịch → dùng tham lam: cộng tất cả prices[i] - prices[i-1] > 0.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
int dp[N+5][N+5][2];

class Solution {
public:
    void pre() {
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= N; j++)
                dp[i][j][0] = dp[i][j][1] = -1;
    }

    int solve(vector<int>& arr, int i, int n, int k, int hold) {
        if (i == n) return hold ? -100000 : 0;
        if (dp[i][k][hold] != -1) return dp[i][k][hold];
        int ans = solve(arr, i+1, n, k, hold);
        if (hold) {
            ans = max(ans, solve(arr, i+1, n, k-1, 0) + arr[i]);
        } else if (k > 0) {
            ans = max(ans, solve(arr, i+1, n, k, 1) - arr[i]);
        }
        return dp[i][k][hold] = 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);
    }
};

int main() {
    Solution ob;
    vector<int> v = {3, 2, 6, 4, 0, 3};
    cout << ob.maxProfit(2, v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n * k) (với memoization).
• Không gian: O(n * k).
• Trường hợp k ≥ n/2: O(n).

Input / Output

Input:  {3,2,6,4,0,3}, k=2
Output: 7