Pat class A - 1007 maximum subsequence sum

Link

The question ： Nothing wrong , Is the problem of finding the sum of a maximal subsequence .

Ideas ： Two ideas —— violence 、dp. Violence uses prefix sum to find the maximum difference , But it's still a surprise 1e4 The complexity of is supposed to time out , But the data of this question may be more water 400ms The limit of .

Violence code ：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;

int n, a[N], pre[N], ne;

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        pre[i] = pre[i-1]+a[i];
        if(a[i]<0) ne ++;
    }
    if(ne==n){
        cout << 0 << " " << a[1] << " " << a[n] << endl;
        return 0;
    }
    int ans = 0, bg = 0, ed = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j ++){
            int sum = pre[j]-pre[i-1];
            if(sum>ans){
                ans = sum;
                bg = a[i], ed = a[j];
            }
        }
    }
    cout << ans << " " << bg << " " << ed << endl;

    return 0;
}

dp Code ：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;

int n, a[N];

signed main()
{
    cin >> n;
    int ans = -1, sum = 0, idx = 1;
    int bg = 1, ed = n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
        if(sum<0){
            idx = i+1;
            sum = 0;
        }
        else if(sum>ans){
            ans = sum;
            bg = idx;
            ed = i;
        }
    }
    cout << max(0ll, ans) << " " << a[bg] << " " << a[ed] << endl;

    return 0;
}