UVA 1619 Feel Good - 區間最小值×區間和最大化 (單調棧 + 前綴和)

題目大意

給定長度 n ≤ 100000 的非負整數陣列 a[1..n]。定義區間 [l, r] 的價值 = (∑_{i=l}^r a_i) × min_{i=l}^r a_i。求最大價值區間，輸出最大值及區間 l, r (多解取最短、再取最早)。

核心觀察：以最小值為中心展開

對每個位置 i 作為區間最小值 (即 a[i] 是區間內最小)，最大區間為 [L[i], R[i]]，其中：

• L[i]：向左最遠位置，滿足 a[j] ≥ a[i]。
• R[i]：向右最遠位置，滿足 a[j] ≥ a[i]。

此區間內最小值確為 a[i]，且為以 i 為最小值的最大區間。價值 = a[i] × (prefix[R[i]] - prefix[L[i]-1])。

單調棧 O(n) 求 L[i], R[i]

// L[i]：左側第一個 < a[i] 的位置 + 1
for (int i = 1; i <= n; ++i) {
    L[i] = i;
    if (a[i] > 0) // 0 值不影響最大值 (乘積為 0)，可跳過
        while (a[L[i]-1] >= a[i]) L[i] = L[L[i]-1]; // 跳躍優化
}

// R[i]：右側第一個 < a[i] 的位置 - 1
for (int i = n; i >= 1; --i) {
    R[i] = i;
    if (a[i] > 0)
        while (a[R[i]+1] >= a[i]) R[i] = R[R[i]+1];
}

跳躍優化：L[L[i]-1] 直接跳到上一個更小元素的左邊界，攤還 O(1)。等同於單調棧邏輯但代碼更簡潔。

前綴和 + 枚舉計算答案

prefix[0] = 0;
for (int i = 1; i <= n; ++i) prefix[i] = prefix[i-1] + a[i];

long long ans = 0;
int bestL = 1, bestR = 1;
for (int i = 1; i <= n; ++i) {
    if (a[i] == 0) continue; // 價值為 0
    long long val = 1LL * a[i] * (prefix[R[i]] - prefix[L[i]-1]);
    if (val > ans) {
        ans = val; bestL = L[i]; bestR = R[i];
    } else if (val == ans) {
        // 同值取最短區間
        if (bestR - bestL > R[i] - L[i] || 
           (bestR - bestL == R[i] - L[i] && L[i] < bestL)) {
            bestL = L[i]; bestR = R[i];
        }
    }
}

完整代碼要點

• 多測資，案例間輸出空行。
• long long 防溢出 (1e5 × 1e6 × 1e5 = 1e16 超 32 位)。
• 陣列大小 1000010 留餘量。
• UVA 判題機制特殊，建議去 POJ 3690 提交 (同題)。

複雜度

• 時間：O(n) (單調棧跳躍 + 單次掃描)。
• 空間：O(n)。