acdream 1682(有環的最大連續和)

acdream 1682(有環的最大連續和)

題意：有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;
}