[C++知识库]Problem - 1003: Max Sum

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 375054
Accepted Submission(s): 90051

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.
给定一个序列 a[1],a[2],a[3]…a[n]，你的任务是找出和最大的子序列。比如，给的序列是 (6,-1,5,4,-7)，那么这个在这个序列中和子序列的最大和为 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).
输入的第一行包含一个整数T(1≤T≤20)，表示测试用例的数量。接下来会输入T行，每一行以数字N开始(1≤N≤100000)，然后是N个整数（所有整数都在-1000到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.
对于每个测试用例，您应该输出两行。第一行是“Case #:”，#表示测试用例的编号。第二行包含三个整数，序列中的Max Sum，最大和的子序列的起始位置，结束位置。如果有多个结果，则输出第一个结果。每两个结果之间有一空行。

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

Author【作者】

Ignatius.L

Recommend【相关推荐】

We have carefully selected several similar problems for you: 1176 1087 1069 2084 1058

My Code in C++【我的C++代码】

#include<iostream>
using namespace std;

struct cell { int start, end, sum; }; //子序列标识

cell dp(int* L) {
    cell o = { 1, 1, L[1] }, max = o;
    for (o.end = 2; o.end <= L[0]; o.end++) {
    //我们用sum_{end}表示序列L中以第end个元素结尾的序列的最大子段和
    //那么有sum_{end} = max{ sum_{end - 1} + L_{end}, L{end} }
    //随着end在序列中的前进，要根据max的选择调整当前的start、sum的值
        int sum = o.sum + L[o.end];
        if (sum >= L[o.end]) o.sum = sum;
        else {
            o.start = o.end;
            o.sum = L[o.end];
        }
        if (sum >= max.sum) max = o; //记录从头到尾sum值最大的序列标识
    }
    return max;
}

int main() {
    int T, ** LL, i, j, t;
    cell max;
    cin >> T;
    LL = new int* [T];
    for (i = 0; i < T; i++) { //读入T个序列
        cin >> t;
        LL[i] = new int[t + 1];
        LL[i][0] = t;
        for (j = 1; j <= t; j++) cin >> LL[i][j];
    }
    for (i = 0; i < T; i++) { //处理测试用例并输出结果
        max = dp(LL[i]);
        cout << "Case " << i + 1 << ":" << endl << max.sum << " " << max.start << " " << max.end << endl;
        if (i < T - 1) cout << endl;
    }
    return 0;
}

Realtime Status【测试结果】