Maximum Profit จากการซื้อขายหุ้นสูงสุด 2 ครั้ง

ในการซื้อขายหุ้น ภายในวันเดียวอนุญาตให้ทำธุรกรรมได้สูงสุด 2 ครั้ง (ซื้อ-ขาย ครั้งที่ 1 ต้องเสร็จก่อนครั้งที่ 2 จะเริ่ม) กำหนดราคาหุ้นแต่ละวัน ต้องการหา กำไรสูงสุด ที่เป็นไปได้

ตัวอย่าง Input และ Output

Input: {2, 30, 15, 10, 8, 25, 80}
Output: Maximum Profit = 100

วิธีทำ:
- ครั้งที่ 1: ซื้อที่ 2, ขายที่ 30 → กำไร 28
- ครั้งที่ 2: ซื้อที่ 8, ขายที่ 80 → กำไร 72
- รวม = 28 + 72 = 100

อัลกอริทึม Dynamic Programming (2 Passes)

ฟังก์ชัน findMaxProfit(pricelist, n)

แนวคิด: 2 Phase

1. Pass 1 (ขวาไปซ้าย): คำนวณกำไรสูงสุดจาก การขายครั้งเดียว ในช่วง [i, n-1]
   • เก็บใน profit[i]
   • ติดตาม maxPrice (ราคาสูงสุดที่เจอจากขวา)
2. Pass 2 (ซ้ายไปขวา): รวมกำไรจาก การซื้อครั้งที่ 2 ในช่วง [0, i]
   • ติดตาม minPrice (ราคาต่ำสุดจากซ้าย)
   • profit[i] = max(profit[i-1], profit[i] + (price[i] - minPrice))
3. คำตอบ = profit[n-1]

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

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

    // Pass 1: ขวาไปซ้าย - หากำไรขายครั้งเดียวจาก i ถึง n-1
    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]);
    }

    // Pass 2: ซ้ายไปขวา - รวมกำไรซื้อครั้งที่ 2
    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));
    }

    int result = profit[n-1];
    delete[] profit;
    return result;
}

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

Output

Maximum Profit = 100

ความซับซ้อน

• Time: O(n) - ผ่านอาร์เรย์ 2 ครั้ง
• Space: O(n) - อาร์เรย์ profit

การขยาย: k Transactions

สำหรับ k transactions ทั่วไป ใช้ DP 3 มิติ: dp[k][i] = กำไรสูงสุด k transactions จนถึงวัน i - Time: O(k × n²) หรือ O(k × n) ด้วยการ optimize