最大连续子段和（动态规划，递归，递推）

 状态设计：dp[i]表示以a[i]结尾的最大序列和

  状态转移方程： dp[i]=max(a[i],dp[i-1]+a[i]);

/**
    状态设计：dp[i]表示以a[i]结尾的最大序列和
    状态转移方程： dp[i]=max(a[i],dp[i-1]+a[i]);
*/

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << "输入整数的个数:\n";
    cin >> n;
    cout << "输入 " << n  << " 个整数:\n";
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    int ans=a[0];
    int dp[n];  //dp[i]表示以a[i]结尾的最大序列和
    dp[0]=a[0];
    for(int i=1;i<n;++i)
    {
        dp[i]=max(a[i],dp[i-1]+a[i]);
        ans=max(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

求序列的最大连续子段和，如果全为负数，则最大连续最大字段和为0
 并且还要输出最大子段和的开始和结束下标

/**
    求序列的最大连续子段和，如果全为负数，则最大连续最大字段和为0
    并且还要输出最大子段和的开始和结束下标
*/

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << "输入整数的个数:\n";
    cin >> n;
    cout << "输入 " << n  << " 个整数:\n";
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    int ans=0,this_sum=0;
    int sum_start=0,sum_end=0;
    int start=0;
    for(int i=0;i<n;++i)
    {
        this_sum+=a[i];
        if(this_sum>ans)
        {
            ans=this_sum;
            sum_start=start;
            sum_end=i;
        }
        else if(this_sum<0)
        {
            start=i+1;
            this_sum=0;
        }
    }
    cout << "max_sum: " << ans << endl;
    cout << "max_sum_start_index: " << sum_start << endl;
    cout << "max_sum_end_index: " << sum_end << endl;
    return 0;
}

二分法求解，具有重叠子问题，用递归则要中间进行一些处理操作。

/**
    二分法求解
*/

#include <iostream>
#include <cstdio>
using namespace std;
int max_sum(int *a,int l,int r);
int max_sum_3(int *a,int n);
int main()
{
    int n;
    printf("输入数据个数:\n");
    cin >> n;
    int a[n];
    printf("输入%d个数:\n",n);
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
    }
    int sum=max_sum_3(a,n-1);
    cout << sum << endl;
    return 0;
}

//一直二分下去，直到只有一个数，才到终止条件
int max_sum(int *a,int l,int r)
{
    if(l==r)
    {
        if(a[l]>0)
            return a[l];
        else
            return 0;
    }
    int mid=l+(r-l)/2;
    int lmax=max_sum(a,l,mid);
    int rmax=max_sum(a,mid+1,r);
    int ltempmax=0,tempsum=0;
    for(int i=mid;i>=l;--i)
    {
        tempsum+=a[i];
        if(tempsum>ltempmax)
            ltempmax=tempsum;
    }
    tempsum=0;
    int rtempmax=0;
    for(int i=mid+1;i<=r;++i)
    {
        tempsum+=a[i];
        if(tempsum>rtempmax)
            rtempmax=tempsum;
    }
    int midmax=ltempmax+rtempmax;
    if(lmax>rmax)
    {
        if(lmax>midmax)
            return lmax;
    }
    else
    {
        if(rmax>midmax)
            return rmax;
    }
    return midmax;
}

int max_sum_3(int *a,int n)
{
    return max_sum(a,0,n-1);
}