PROG-T1005: Max Sequence

#include <bits/stdc++.h>
using namespace std;

const int N = 2500;

int arr[N + 1], dp[N + 1], par[N + 1];
int nSeq;

int main(){

    scanf("%d", &nSeq);
    for(int i = 1; i <=  nSeq; ++i){
        scanf("%d", &arr[i]);
    }

    int bestIdx = 0;
    int ans = -1e9;
    for(int i = nSeq; i >= 1; --i){
        if(arr[i] > arr[i] + dp[i + 1]){
            dp[i] = arr[i];
            par[i] = i;
        } else {
            dp[i] = arr[i] + dp[i + 1];
            par[i] = i + 1;
        }
        if(dp[i] > ans){
            ans = dp[i];
            bestIdx = i;
        }
    }

    if(ans <= 0){
        cout << "Empty sequence";
    } else {
        int i = bestIdx;
        cout << arr[i] << " ";
        while(par[i] != i){
            i = par[i];
            cout << arr[i] << " ";
        }
        cout << "\n" << ans;
    }

    return 0;
}