题解 | #最大连续子序列#

动态规划，用结构体记录子序列起始元素和起始下标

#include <climits>
#include <iostream>
#include "vector"
#include "algorithm"
using namespace std;
struct biggestSubSeq {
    long long start;
    long long end;
    long long sum;
    int startIndex;
    int endIndex;
    biggestSubSeq(long long a, long long b, long long c,int d,int e) {
        start = a;
        end = b;
        sum = c;
        startIndex=d;
        endIndex=e;
    };
    bool operator>(biggestSubSeq B) {
        if (sum == B.sum) {
            if (startIndex != B.startIndex) return startIndex < B.startIndex;
            else return endIndex < B.endIndex;
        } else {
            return sum > B.sum;
        }
    }
};
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<long long> sequence;
        vector<biggestSubSeq> dp;
        if (n == 0) break;
        while (n--) {
            long long temp;
            cin >> temp;
            sequence.push_back(temp);
            dp.push_back(biggestSubSeq(0, 0, 0,0,0));
        }
        dp[0] = biggestSubSeq(sequence[0], sequence[0], sequence[0],0,0);
        biggestSubSeq biggestSeq = dp[0];

        for (int i = 1; i < sequence.size(); i++) {
            dp[i].sum = max(sequence[i], dp[i - 1].sum + sequence[i]);
            if (sequence[i] > dp[i - 1].sum + sequence[i]) {
                dp[i].start = dp[i].end = sequence[i];
                dp[i].startIndex = dp[i].endIndex = i;
            } else {
                dp[i].start = dp[i - 1].start;
                dp[i].startIndex = dp[i-1].startIndex;
                dp[i].endIndex =i;
                dp[i].end = sequence[i];
            }
            if (dp[i] > biggestSeq) {
                biggestSeq = dp[i];
            }
        }
        if (biggestSeq.sum <= 0) biggestSeq = biggestSubSeq(sequence[0],
                                                 sequence[sequence.size()-1], 0,0,sequence.size()-1);
        cout << biggestSeq.sum << ' ' << biggestSeq.start << ' ' << biggestSeq.end <<
             endl;
    }
}
// 64 位输出请用 printf("%lld")