最大子段和什么意思_求最大子段和

#include<iostream>

using namespace std;

int main()
{
    int a[20];
    int n;
    int max=0;
    int x,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)  //左区间
    {
        for(int j=i;j<=n;j++)  //右区间
        {
            int sum=0;
            for(int k=i;k<=j;k++)  //区间内的和
            {
                sum+=a[k];
            }
            if(sum>max)
            {
                max=sum;
                x=i,y=j;
            }
        }
    }
    if(max>0)
    {
        cout<<max<<" , ["<<x<<" , "<<y<<"]";
    }
    else
    {
        cout<<0;
    }
    return 0;
}

#include<iostream>
using namespace std;

int MaxSubArray(int a[],int left,int right)
{
    int mid=(left+right)/2;
    int s1,s2,sum=0;
    int max=-10000;  //max相当于s3
    if(left==right)
    {
        return a[left];
    }
    s1=MaxSubArray(a,left,mid);  //左递归
    s2=MaxSubArray(a,mid+1,right);  //右递归
    for(int i=mid;i>=0;i--)   //从左半部分最后一个数向前加找出最大值
    {
        sum+=a[i];
        if(max<sum)
        {
            max=sum;
        }
    }
    sum=max;  //保留最大值
    for(int i=mid+1;i<=right;i++)    //从右半部分第一个数向后加找出最大值
    {
        sum+=a[i];
        if(max<sum)
        {
            max=sum;
        }
    }
    if(max<s1)
    {
        max=s1;
    }
    else if(max<s2)
    {
        max=s2;
    }return max;
}
int main()
{
    int a[20];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<MaxSubArray(a,0,n-1);
    return 0;
}

#include<iostream>

using namespace std;

void MaxSubArray(int a[],int D[],int Rec[],int n)
{
    int max=n;
    for(int i=n-1;i>=0;i--)  //从倒数第二个元素开始
    {
        if(D[i+1]>0)
        {
            D[i]=D[i+1]+a[i];
            Rec[i]=Rec[i+1];
        }
        else
        {
            D[i]=a[i];
            Rec[i]=i+1;
        }
        if(D[i]>D[max])
        {
            max=i;
        }
    }
    cout<<D[max]<<" , ["<<max+1<<" , "<<Rec[max]<<"]";
}
int main()
{
    int a[20];
    int D[20];
    int Rec[20];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];

    }
    Rec[n-1]=n;D[n-1]=a[n-1];
    MaxSubArray(a,D,Rec,n-1);
    return 0;
}