最大子段和（分治递归）（动态规划）_数列最大子段和分治法递归

【问题描述】使用分治递归算法解最大子段和问题，具体来说就是，将序列分为长度相等的左右两段，分别求出这两段的最大子段和，包含左右部分子段的最大子段和，求这三种情况得到的最大子段和的最大值。

【输入形式】在屏幕上输入一个序列元素，包含负整数、0和正整数。

【输出形式】序列的最大子段和，及得到最大子段和时的起始和终止编号。

【样例输入】

 -2 11 -4 13 -5 -2

【样例输出】

 20

 2

 4

【样例说明】

 输入：6个数，元素间以空格分隔。

 输出：序列的最大子段和20，得到最大子段和时的起始编号为2，终止编号为4。

【评分标准】根据输入得到准确的输出。

分治递归：

//分治法
#include<bits/stdc++.h>
int a[1000];
using namespace std;

int max(int a,int b,int c){
    if(a>=b&&a>=c) return a;
    if(b>=a&&b>=c) return b;
    else return c;
}

int divide_max(int a[],int left,int right,int &l,int &r)
{
    int sum=0;
    int i;
    int l1,l2,l3,r1,r2,r3;
    if(left==right)
    {
        if(a[left]>0)
        {
        l=left;//起始位置
        r=left;//结束位置     
        return a[left] ;
        }
        else return 0;
    }
    
    int center=(left+right)/2;
    int left_sum=divide_max(a,left,center,l1,r1);
    int right_sum=divide_max(a,center+1,right,l2,r2);
    
    int s1=0;
    int lefts=0;
    for(i=center;i>=left;i--)
    {
        lefts=lefts+a[i];
        if(lefts>s1)
        {
        s1=lefts;
        l3=i;
        }
        
    }
    
    int s2=0;
    int rights=0;
    for(i=center+1;i<=right;i++)
    {
        rights=rights+a[i];
        if(rights>s2)
        {
        s2=rights;
        r=i;
        r3=i;
        }
        
        
    }
    
    sum=s1+s2;
    l=l3,r=r3;
    if(sum<=left_sum) sum=left_sum,l=l1,r=r1;
    if(sum<=right_sum) sum=right_sum,l=l2,r=r2;
    return sum;
    
}
int main()
{
    
    int number,n=1;
    string s;
    getline(cin,s);
    stringstream ss(s);
    while (ss>>number)
    {
        a[n++]=number;
    }
    
    //int a[6]={-2,11,-4,13,-5,-2};
    int l=1,r=1;
    int b=divide_max(a,1,n-1,l,r);
    cout<<b<<endl;
    cout<<l<<endl;
    cout<<r<<endl;
    return 0;
}

动态规划：

#include<bits/stdc++.h>
using namespace std;
int a[1000];

void dynamic_max(int a[], int n){
    int sum=0;
    int b=0;
    int r=0,l=0;
    int left=0,right=0;
    for(int i=1;i<=n;i++)
    {
        if(b>0)
        {
        b+=a[i];
        r=i;    
        }
        else {
        b=a[i];    
        l=r=i;
        }
        if (b>sum)
        {
        sum=b;    
        left=l;
        right=r;
        }
    }
    
    
    cout<<sum<<endl;
    cout<<left<<endl;
    cout<<right<<endl;
    
}
 
int main()
{
    
    int number,n=0;
    string s;
    getline(cin,s);
    stringstream ss(s);
    while (ss>>number)
    {
        a[++n]=number;
    }
    //int a[6]={-2,11,-4,13,-5,-2};
    dynamic_max(a,n);
    
    return 0;
}