Lợi nhuận tối đa mua/bán cổ phiếu tối đa 2 lần

Cho mảng giá cổ phiếu theo thời gian. Cho phép tối đa 2 giao dịch (mua rồi bán, giao dịch 2 chỉ bắt đầu sau khi giao dịch 1 kết thúc). Tìm lợi nhuận tối đa.

Đầu vào và Đầu ra

Đầu vào: {2, 30, 15, 10, 8, 25, 80}
Đầu ra: Maximum Profit = 100
(Giao dịch 1: mua 2 bán 30 → 28. Giao dịch 2: mua 8 bán 80 → 72. Tổng = 100)

Thuật toán (2 lần duyệt)

1. Mảng profit[n] khởi tạo 0.
2. Duyệt **ngược** (từ phải sang trái): theo dõi maxPrice (giá cao nhất thấy được). profit[i] = max(profit[i+1], maxPrice - price[i]) → lợi nhuận tối đa từ i đến cuối với 1 giao dịch.
3. Duyệt **xuôi** (từ trái sang phải): theo dõi minPrice. profit[i] = max(profit[i-1], profit[i] + price[i] - minPrice) → cộng thêm lợi nhuận giao dịch 1 kết thúc tại i.
4. Kết quả: profit[n-1].

Ví dụ C++

#include <iostream>
using namespace std;

int max(int a, int b) { return (a>b)?a:b; }

int findMaxProfit(int priceList[], int n) {
    int *profit = new int[n];
    for(int i=0;i<n;i++) profit[i]=0;

    int maxPrice = priceList[n-1];
    for(int i=n-2;i>=0;i--) {
        if(priceList[i] > maxPrice) maxPrice = priceList[i];
        profit[i] = max(profit[i+1], maxPrice - priceList[i]);
    }

    int minPrice = priceList[0];
    for(int i=1;i<n;i++) {
        if(priceList[i] < minPrice) minPrice = priceList[i];
        profit[i] = max(profit[i-1], profit[i] + (priceList[i] - minPrice));
    }
    return profit[n-1];
}

int main() {
    int priceList[] = {2,30,15,10,8,25,80};
    cout << "Maximum Profit = " << findMaxProfit(priceList,7);
}

Kết quả

Maximum Profit = 100