c.cpp

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;


int main(int argc, char *argv[])
{
//	freopen("input", "r", stdin);

	int t, n;
	int left[50000], right[50000];
	int a[50000];

	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		int M1 = -10001, M2 = -10001;
		int sum = 0;
		int poscnt = 0;
		int midx;

		for (int i = 0; i < n; i++) {
			sum += a[i];
			if (a[i] > 0)
				poscnt++;
			if (a[i] > M1) {
				M1 = a[i];
				midx = i;
			}
		}
		if (poscnt <= 2) {
			for (int i = 0; i < n; i++)
				if (a[i] > M2 && i != midx)
					M2 = a[i];
			printf("%d\n", M1 + M2);
			continue;
		}

		memset(left, 0, sizeof(left));
		memset(right, 0, sizeof(right));

		int presum = 0, maxsum = 0;
		for (int i = 0; i < n - 1; i++) {
			presum += a[i];
			if (presum < 0) {
				presum = 0;
			} else if (presum > maxsum) {
				maxsum = presum;
			}
			left[i] = maxsum;
		}

		presum = 0, maxsum = 0;
		for (int i = n - 1; i > 0; i--) {
			presum += a[i];
			if (presum < 0) {
				presum = 0;
			} else if (presum > maxsum) {
				maxsum = presum;
			}
			right[i - 1] = maxsum;
		}
		int result = 0;
		for (int i = 0; i < n - 1; i++) {
			result = max(result, left[i] + right[i]);
		}


		presum = 0;
		int minsum = 0;
		for (int i = 1; i < n - 2; i++) {
			presum += a[i];
			if (presum > 0) {
				presum = 0;
			} else if (presum < minsum) {
				minsum = presum;
			}
			left[i] = minsum;
		}

		presum = 0, minsum = 0;
		for (int i = n - 2; i > 1; i--) {
			presum += a[i];
			if (presum > 0) {
				presum = 0;
			} else if (presum < minsum) {
				minsum = presum;
			}
			right[i - 1] = minsum;
		}
		int sub = 0;
		for (int i = 1; i < n - 2; i++) {
			sub = min(sub, left[i] + right[i + 1]);

		}

		result = max(result, sum - sub);
		printf("%d\n", result);
	}

	return 0;
}