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<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
DP问题。注意数组必须要开到100000以上才可以。
思路大体是开一个临时的子串并不断跟sum进行比较。复习一下动态规划再看。
代码：
#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 < tSum)
{
sum = tSum;
first = tFirst;
last = i;
}
}
}
int main()
{
int num, n, i, j;
bool top = true;
cin >> 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 << endl;
cout << "Case " << j + 1 << ":" << endl
<< sum << " " << first + 1 << " "
<< last + 1 << endl;
delete[] arr;
}
return 0;
}
//求最大子序列之和，arr是原来的数组，count是数组的元素个数,
//first,last是所求子序列的第一个元素，最后一个元素的下标，sum是所求子序列的元素之和
部分参考自网络。
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆除注明外，本站文章均为原创；转载时请保留上述链接。