HDOJ1003:Max Sum——简单动态规划

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 

部分参考自网络。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注