Lợi nhuận tối đa mua bán cổ phiếu trong C++

Mô tả bài toán

Cho mảng stkprice[] giá cổ phiếu theo ngày. Tìm lợi nhuận tối đa từ nhiều giao dịch (mua bán nhiều lần), không thể giữ nhiều vị thế cùng lúc.

Ví dụ: {120, 310, 405, 210, 150, 550} → Mua ngày 1 bán ngày 3 (lãi 285), mua ngày 5 bán ngày 6 (lãi 400) → Tổng 685.

Giải pháp (Cực trị cục bộ)

• Tìm các cực tiểu cục bộ (mua) và cực đại cục bộ (bán) liền sau.
• Tổng lợi nhuận = tổng price[max] - price[min] cho mỗi cặp.
• Độ phức tạp O(N), không gian O(1).

Ví dụ minh họa

#include <iostream>
using namespace std;

void MaximizeProfit(int price[], int n) {
    if (n == 1) return;
    int maxProfit = 0, i = 0;
    while (i <= n - 1) {
        while (i <= n - 2 && price[i+1] <= price[i]) i++;
        int minima = i++;
        while (i < n && price[i] >= price[i-1]) i++;
        int maxima = i - 1;
        maxProfit += price[maxima] - price[minima];
        // cout << "Buy day " << minima+1 << " Sell day " << maxima+1 << " profit " << price[maxima]-price[minima] << "\n";
    }
    cout << "The maximized profit is " << maxProfit;
}

int main() {
    int stkPrice[] = {120, 310, 405, 210, 150, 550};
    int days = 6;
    MaximizeProfit(stkPrice, days);
    return 0;
}

Đầu ra

The maximized profit is 685