HDU 5280 Senior's Array：必修改一元素為 P 後的最大區間和

題目大意

給定 n 個整數，必須將恰好一個元素修改為 P。求修改後數組的最大區間和（子數組和）。

分類討論

對任一區間 [l, r]，有兩種情況：

1. 修改在區間外：區間和不變，為 sum[r] - sum[l-1]。
2. 修改在區間內：為了最大化區間和，應將區間內最小元素修改為 P。新和 = 原和 - minVal + P。

枚舉所有區間，取上述兩種情況的最大值。特殊情況：區間覆蓋整個數組時，必須在區間內修改，只能用情況 2。

預處理與枚舉

預處理前綴和 sum[i]。
雙重循環枚舉左端點 l，維護區間最小值 minVal，右端點 r 擴展時更新 minVal = min(minVal, a[r])。
對每個 [l, r] 計算兩種候選值，更新全局答案。

複雜度

O(n²) 枚舉區間，n ≤ 1000（HDU 5280 實際限制），完全可行。若 n 更大可用單調棧優化至 O(n log n) 或 O(n)，但題目數據範圍允許 O(n²)。

C++ 實現