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

利用map来跟踪最大子序列和中所有元素
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<limits>
using namespace std;
#define N 10005


int arr[N];
int dp[N];
map<int, int> mymap;

int Maxsublength(int n) {
    int maximal = -1000;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i] = arr[i];
        } else {
            if (dp[i - 1] + arr[i] > arr[i])
                mymap[i] = i - 1;  // 将dp[i]->dp[i-1]
            dp[i] = max(arr[i], dp[i - 1] + arr[i]);
        }
        maximal = max(maximal, dp[i]);
    }

    return maximal;


}




int main() {
    int n;
    while (cin >> n) {
        if (n == 0) return 0;
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        mymap.clear();
        bool flag = false;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            if (arr[i] >= 0) flag = true;
        }
        if (flag == false) {
            cout << 0 << ' ' << arr[0] << ' ' << arr[n - 1] << endl;
            continue;
        }
        int res = Maxsublength(n);
        cout << res << ' ';
        int flag1;
        for (int i = 0; i < n; i++) {
            if (res == dp[i]) {
                flag1 = i;  //拿到最后一个元素
                break;
            }

        }
        int i;
        for (i = flag1; mymap.find(i) != mymap.end();) {
            i = mymap[i];
        }
        cout << arr[i] << ' ';
        cout << arr[flag1] << endl;

    }



}