# 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