Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1 #include #include #include #include #include #include using namespace std; int n, s, e; int a[100002]; int maxsub(int a[]) { s = e = 1; int sum, j, b, bs, be; sum = b = a[0]; for (j = 0; j= 0 && j != 0) { b = b + a[j]; be = j + 1; } else { b = a[j]; bs = j + 1; be = j + 1; } if (b>sum) { sum = b; s = bs; e = be; } } return sum; } int main() { int t, i, k = 1, sum; scanf(“%d”, &t); while (t–) { scanf(“%d”, &n); for (i = 0; i

另一版本

#include 
using namespace std;
int *arr, first, last, sum;
void MaxSub(int *arr, int count, int &first, int &last, int ∑)
{
	//tFirst,tSum为临时的最大子序列的第一个元素与和
	int tFirst, tSum, i;
	//初始化
	first = tFirst = last = 0;
	sum = tSum = arr[0];
	//遍历该数组
	for (i = 1; i= 0)
			tSum += arr[i];
		else
		{
			tSum = arr[i];
			tFirst = i;
		}
		//如果临时的最大值大于实际的最大值，则更新子序列的first, last, sum
		if (sum > num;
	for (j = 0; j> n;
		arr = new int[n];
		for (i = 0; i> arr[i];
		MaxSub(arr, n, first, last, sum);
		if (top)
			top = false;
		else
			cout 
部分参考自网络。
原文标题：HDOJ1003：Max Sum——简单动态规划|落絮飞雁的个人网站
原文链接：https://www.luoxufeiyan.com/2015/03/15/hdoj1003/
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆
除注明外，本站文章均为原创；转载时请保留上述链接。