01-复杂度2 Maximum Subsequence Sum   (25分)

Given a sequence of K
integers { N1,N2,
…, NK
}. A continuous subsequence is defined to be { Ni,Ni+1,
…, Nj
} where 1ijK.
The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

### Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integerK
(10000).
The second line contains K
numbers, separated by a space.

### Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence
is not unique, output the one with the smallest indices i
and j
(as shown by the sample case). If all the K
numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

### Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21
</pre> ### Sample Output: <pre>10 1 4

#include  /
author：Fayne   time:2015-9-2 21:24:16
thisSum用于保存临时序列之和，maxSum更新最大序列和  left, right分别表示最大序列的左右序号，tempLeft保存临时左端的序号
/using namespace std;int A;int main(){    int k, i;    cin >> k;    for ( i=0; i<k; i++ )        cin >> A[i];    int left = 0, right = k-1, maxSum = -1, thisSum = 0, tempLeft;//maxSum赋初值为-1为了解决出现全部序列为负的情况    for ( i=0; i<k; i++ )    {        thisSum += A[i];        if ( thisSum > maxSum )//如果临时序列和大于最大和，则更新最大和        {            maxSum = thisSum;            left = tempLeft;//将临时左端的序号赋值给左端序号            right = i;        }        else if ( thisSum < 0 )//thisSum小于0时，从此刻下一个开始重新求和        {            thisSum = 0;            tempLeft = i+1;//把此刻的下一序号赋值给临时左端序号        }    }    if ( maxSum < 0 )//maxSum < 0 说明整个序列全为负数，根据题意，最大和应该为0        maxSum = 0;    cout << maxSum << “ “ << A[left]<< “ “ << A[right]<< endl;    return 0;}

numbers are negative, then its maximum sum is defined to be 0

• 本文作者： Fayne
• 本文链接： 371.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！