題意:有n個數字圍成一個圈,然後從圓圈拿走連續的一些數,問拿走的數的和的最大值是多少。
題解:普通最大連續和的做法,如果前面累加的數加當前數是大於最大值就更新最大值,如果小於0就把累加值清零,這個是有環的,那麼可以從兩種情況考慮,一種是普通的最大連續和找到的最大值,另一種就是頭尾拼接的,把所有數取相反數,然後找到最大連續和,那麼用總和sum加這個數就是頭尾拼接的最大值,取兩種情況較大的就是解。
#include#include using namespace std; const int N = 200010; int n, s[N]; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); int sum = 0; for (int i = 1; i <= n; i++) { scanf("%d", &s[i]); sum += s[i]; } int res = 0, maxx = 0; for (int i = 1; i <= n; i++) { res += s[i]; if (res > maxx) maxx = res; if (res < 0) res = 0; } for (int i = 1; i <= n; i++) s[i] = -1 * s[i]; int res2 = 0, maxx2 = 0; for (int i = 1; i <= n; i++) { res2 += s[i]; if (res2 > maxx2) maxx2 = res2; if (res2 < 0) res2 = 0; } printf("%d\n", max(maxx, sum + maxx2)); } return 0; }