題目描述
小 A 喜歡坐地鐵。地鐵環線有 n n n 個車站，依次以 1 , 2 , ? , n 1,2,\cdots,n 1,2,?,n 標號。車站 i ( 1 ≤ i < n ) i\ (1\leq i<n) i?(1≤i<n) 的下一個車站是車站 i + 1 i+1 i+1。特殊地，車站 n n n 的下一個車站是車站 1 1 1。
小 A 會從某個車站出發，乘坐地鐵環線到某個車站結束行程，這意味著小 A 至少會經過一個車站。小 A 不會經過一個車站多次。當小 A 乘坐地鐵環線經過車站 i i i 時，小 A 會獲得 a i a_i ai? 點快樂值。請你安排小 A 的行程，選擇出發車站與結束車站，使得獲得的快樂值總和最大。
輸入格式
第一行，一個正整數 n n n，表示車站的數量。
第二行， n n n 個整數 a i a_i ai?，分別表示經過每個車站時獲得的快樂值。
輸出格式
一行，一個整數，表示小 A 能獲得的最大快樂值。
輸入輸出樣例 #1
輸入 #1
4
-1 2 3 0
輸出 #1
5
輸入輸出樣例 #2
輸入 #2
5
-3 4 -5 1 3
輸出 #2
5
說明/提示
對于 20 % 20\% 20% 的測試點，保證 1 ≤ n ≤ 200 1\leq n\leq 200 1≤n≤200。
對于 40 % 40\% 40% 的測試點，保證 1 ≤ n ≤ 2000 1\leq n\leq 2000 1≤n≤2000。
對于所有測試點，保證 1 ≤ n ≤ 2 × 10 5 1\leq n\leq 2\times 10^5 1≤n≤2×105， ? 10 9 ≤ a i ≤ 10 9 -10^9\leq a_i\leq 10^9 ?109≤ai?≤109。
solution
求區間和的最大值和最小值，區間和的最小值意味著互補區間的最大值，兩者中更大的為結果
代碼
#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"using namespace std;long long n, x, Min = 1e9, Max = -1e9, s, MMin = 2e9, MMax = -2e9;int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> x;s += x;MMin = min(MMin, s - Max);MMax = max(MMax, s - Min);Min = min(Min, s);Max = max(Max, s);}cout << max(s - MMin, MMax);
}
結果
)
