Question

帮我解决一道C语言算法的问题

题目是这样的
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).

(2007-08-08 13:42:29) wit saying(644302084)
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

我需要算法分析！谢谢~越详细越好，采纳再加分！

Answer 1

这是一个最大子序列和问题。通常用动态规划法解。至于动态规划的数学模型，懒得去查了，直接给你找了一个算法，你凑合看吧。

从整数序列头部开始扫描，假设现扫描到的位置为i，求取从0到i所有元素的和sum[i]，sum[i]取最大值的地方即为最大子序列的结束位置，设为a。从结束位置a向前扫描，找到第一个小于零的位置b，b+1就是最大子序列的开始位置。求从b+1到a位置的值即可得到最大子序列和。按此思路该算法时间复杂度为O(m+n)，其中m, n分别为最大子序列的长度、给定整数序列的长度。
改进：根据对上述算法的进一步分析，可以知道，最大子序列和中必然不存在前缀子序列小于0的情况，于是设一ThisSum用于指示当前子序列和。改进算法描述如下：从整数序列头部开始扫描，累加序列元素和ThisSum，若ThisSum<0，则停止累加子序列和，将ThisSum清零，并从下一位置重新开始累加ThisSum，否则将ThisSum与当前MaxSum比较，并更新MaxSum。此改进算法时间复杂度仅为O(n)，n为给定整数序列的长度。

int MaxSubsequenceSum3(const int A[], int N)

{

int ThisSum, MaxSum, i;

ThisSum = MaxSum = 0;

for(i = 0; i < N; i++)

{

ThisSum += A[i];

if(ThisSum > MaxSum)

MaxSum = ThisSum;

else if(ThisSum < 0)

ThisSum = 0;

}

return MaxSum;

}

Answer 2

给出一个序列a[1],a[2],a[3]......a[n],你的工作是算出子序列和的最大值,比如给出一个序列6,-1,5,4,-7),那么它的子序列和的最大值就是6 + (-1) + 5 + 4 = 14
输入:
输入的第一行是个整数T(1<=T<=20),它是测试序列的和.接下来有T行输入,每行以一个整数N(1<=N<=100000)开始,表示序列的长度为N,接下来就是N个整数(-1000到1000)
输出:
每个测试序列要求有两行输出,第一行表示为"Case #:",基中#测试的序列序号,第二行要有3个整数,分别是子序列和的最大值,以及该子序列的起始位置,终止位置.如果有超过一个序列的输出,就用空行隔开.
例子:
输入:
2 //表示两个序列
5 6 -1 5 4 -7 //第一个5表示这个序列的长度为5
7 0 6 -1 1 -6 7 -5 //第一个5表示这个序列的长度为7
输出
Case 1: //第一个序列的输出结果
14 1 4

Case 2: //第二个序列的输出结果
7 1 6

算法实现:

最直接的方法是从第一个数循环累加,
int a[N];
int startpos=0,endpos=1; //起始位置,终止位置
int max,temp;//最大值
max=a[0];
for(int i=0;i<N;i++)
{
if(a[i]<=0)continue;
temp=a[i];
for(int j=i+1;j<N;j++)
{
temp+=a[j];
if(temp>max)
{
startpos=i;
endpos=j;
max=temp;
}
}
}

Answer 3

读了边题目看出一点：子数列不以 负数 开头或结尾的！

Answer 4

看错了