最长子序列和问题

分而治之：分区间计算每个区间的最大和

#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
int find_maximum_subbarray(int *a,int left, int right)
{
    if(left ==  right)
        return a[left];

        int mid = (left + right) >> 1;
        int left_sum = -0x3f3f3f3f;
        int sum = 0;
        int left_max, right_max;

        int lans = find_maximum_subbarray(a,  left,  mid);
        int rans = find_maximum_subbarray(a,  mid+1, right);

        for(int i = mid; i >= left; i--)
        {
            sum += a[i];
            if (sum > left_sum)
            {
                left_sum = sum;
                left_max = i;
            }

        }
        sum = 0;
        int right_sum = -0x3f3f3f3f;
        for(int i = mid+1; i <= right; i++)
        {
            sum += a[i];
            if (sum > right_sum)
            {
                right_sum = sum;
                right_max = i;
            }
        }

    int ans = left_sum + right_sum;
    if (lans > ans){
        ans = lans;
    }
    if (rans > ans){
        ans = rans;
    }
    return ans;
}
int main(){
    ll n;
    sl(n);
    int * a = new int [n];
    REP(i, 0, n){
        cin >> a[i];
    }
    cout << find_maximum_subbarray( a, 0, n-1);
}

题目：动态规划 dp

#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
int main()
{
    int n;
    si(n);
    int *a = new int [n];
    REP(i, 0, n)
    {
        cin >> a[i];
    }
    int ans = a[0];
    REP_(i, 1, n-1)
    {
        if(a[i - 1] > 0)
        {
            a[i] += a[i-1];
        }
        else
        {
            a[i] +=0;
        }
        if(a[i] > ans)
        {
            ans = a[i];
        }
    }
    cout << ans << endl;
    delete []a;
}