一. 题目

二. 思路

三. 代码

1. dp

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N=1e4+10, INF=2e9;

int n;
int a[N];

class DP
{
public:
    int f[N];
    int maxv, lm, rm;
public:
    DP()
    {
        initIO();
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    void work()
    {
        maxv=-INF, lm=1, rm=n;
        int lt=1, rt;
        for(int i=1;i<=n;++i)
        {
            //f[i]=max(0, f[i-1])+a[i];
            if(f[i-1]<0) f[i]=a[i], lt=rt=i;
            else f[i]=f[i-1]+a[i], rt=i;
            if(f[i]>maxv) lm=lt, rm=rt, maxv=f[i];
        }
        
        if(maxv<0) maxv=0, lm=1, rm=n;
    }
}dp;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp.work();
    cout<<dp.maxv<<" "<<a[dp.lm]<<" "<<a[dp.rm];
}

2. 分治

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        return dfs(0, n-1, nums).maxv;
    }

    Node dfs(int l, int r, int[] nums) {
        if(l>r) return null;
        if(l==r) return new Node(nums[l], nums[l], nums[l], nums[l]);

        int mid=l+r>>1;
        Node ls=dfs(l, mid, nums), rs=dfs(mid+1, r, nums);
        
        if(ls==null) return rs;
        if(rs==null) return ls;

        Node cur=new Node();
        cur.maxv=Math.max(Math.max(ls.maxv, rs.maxv), ls.latMax+rs.preMax);
        cur.preMax=Math.max(ls.preMax, ls.sum+rs.preMax);
        cur.latMax=Math.max(rs.latMax, rs.sum+ls.latMax);
        cur.sum=ls.sum+rs.sum;
        
        return cur;
    }
}

class Node {
    int preMax, latMax;
    int maxv, sum;

    public Node() {}

    public Node(int maxv, int sum, int preMax, int latMax) {
        this.maxv=maxv;
        this.sum=sum;
        this.preMax=preMax;
        this.latMax=latMax;
    }
}