Max Sum HDU - 1003

MAX SUM

分析：
pos[记录]最大片段的左边界

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int dp[maxn];
int pos[maxn];

int main()
{
	int t; cin >> t;
	int cases = 0;
	for (int j = 1; j <= t; j++)
	{
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		dp[1] = a[1], pos[1] = 1;
		int l, r, maxx = dp[1];
		l = r = 1;
		for (int i = 2; i <= n; i++)
		{
			if (dp[i - 1] < 0)
				dp[i] = a[i], pos[i] = i;
			else
				dp[i] = dp[i - 1] + a[i], pos[i] = pos[i - 1];
			if (dp[i] > maxx)
				maxx = dp[i], l = pos[i], r = i;
		}
		printf("Case %d:\n", ++cases);
		printf("%d %d %d\n", maxx, l, r);
		if (j < t)
			cout << endl;
	}
}