หาจำนวนลูกอมสูงสุดที่ซื้อได้ภายใต้เงื่อนไขใน C

โจทย์

กำหนด Array candies[] ที่ candies[i] = จำนวนลูกอมประเภท i

ซื้อ X[i] ลูกอมประเภท i (0 ≤ X[i] ≤ candies[i])

เงื่อนไข: สำหรับทุก j < i ต้องเป็นจริงอย่างน้อย 1 ข้อ:

• X[j] < X[i] (ซื้อประเภท j น้อยกว่า i)
• X[j] = 0 (ไม่ซื้อประเภท j เลย)

→ หมายถึง: **ลำดับการซื้อต้องเพิ่มขึ้นอย่างเคร่งครัด (Strictly Increasing) ถ้าซื้อ** หรือ **ไม่ซื้อเลย (0)**

อัลกอริทึม: Greedy จากท้ายไปหน้า

1. เริ่มจากประเภทสุดท้าย: ซื้อได้มากที่สุด bought = candies[n-1]
2. เดินย้อนกลับ i = n-2 ... 0:
   • ซื้อได้สูงสุด min(candies[i], bought - 1)
   • ถ้า ≤ 0 → ไม่ซื้อประเภทนี้ (X[i] = 0)
   • อัปเดต bought = X[i]
3. รวม X[i] ทั้งหมด

ตัวอย่าง

Input:  {1, 3, 5, 2, 6, 7}
Index:   0  1  2  3  4  5

Start: bought = 7 (index 5)
i=4: min(6, 7-1)=6 → bought=6, total=13
i=3: min(2, 6-1)=2 → bought=2, total=15
i=2: min(5, 2-1)=1 → bought=1, total=16
i=1: min(3, 1-1)=0 → skip
i=0: min(1, 0-1)=0 → skip
Total = 16
X = {0, 0, 1, 2, 6, 7} → Strictly Increasing Non-zero!

โปรแกรม C

#include 

int maxCandies(int arr[], int n) {
    if (n == 0) return 0;
    
    int bought = arr[n - 1];
    int total = bought;
    
    for (int i = n - 2; i >= 0; i--) {
        // Max we can buy at this type
        int can_buy = arr[i] < bought - 1 ? arr[i] : bought - 1;
        
        if (can_buy > 0) {
            total += can_buy;
            bought = can_buy;
        }
        // else: buy 0, bought unchanged (but next must be < 0 → impossible)
    }
    
    return total;
}

int main() {
    int candies1[] = {1, 3, 5, 2, 6, 7};
    int size1 = 6;
    printf("Test 1: %d\n", maxCandies(candies1, size1)); // 16
    
    int candies2[] = {5, 7, 7, 3, 4};
    int size2 = 5;
    printf("Test 2: %d\n", maxCandies(candies2, size2)); // 10
    
    int candies3[] = {1, 2, 4, 3, 7};
    int size3 = 5;
    printf("Test 3: %d\n", maxCandies(candies3, size3)); // 13
    
    return 0;
}

ผลลัพธ์:

Test 1: 16
Test 2: 10
Test 3: 13

Complexity

• Time: O(n) - Single Pass จากท้ายไปหน้า
• Space: O(1) - ใช้ตัวแปรกี่ตัวเท่านั้น

Correctness Proof Sketch

Greedy Choice Property: การซื้อมากที่สุดที่เป็นไปได้ในประเภทสุดท้ายเป็น Optimal เพราะมันไม่จำกัดตัวเลือกของประเภทก่อนหน้า (ซึ่งต้องน้อยกว่า) และให้ "Budget" สูงสุดสำหรับประเภทก่อนหน้า