首页 > > 程序设计 > C/C++ >

最大子段和（分治法）

2018-06-17 23:43:12来源：未知阅读 ()

题目：输入n个数，求最大的连续子段和，并输出子段的起点下标和终点下标；

思路：分治法；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#define N 1000005
using namespace std;
int a[1005];

int calc(int s,int e,int &l,int &r)
{
    int l1,l2,l3,r1,r2,r3;
    ///if(s==e)  return a[s]>0?a[s]:0;
    if(s==e)
    {
        if(a[s]>0)
        {
            l=s;
            r=s;
            return a[s];
        }
        else return 0;
    }
    int mid=(s+e)>>1;
    int sum1=calc(s,mid,l1,r1);
    int sum2=calc(mid+1,e,l2,r2);
    int sl=0,sr=0,t=0;
    for(int i=mid; i>=s; i--)
    {
        t+=a[i];
        if(sl<t) sl=t,l3=i;
    }
    t=0;
    for(int i=mid+1; i<=e; i++)
    {
        t+=a[i];
        if(sr<t) sr=t,r=i,r3=i;
    }
    int ss=sl+sr;
    l=l3,r=r3;
    if(ss<=sum1) ss=sum1,l=l1,r=r1;
    if(ss<=sum2) ss=sum2,l=l2,r=r2;
    return ss;
}

int main()
{
    int n;
    while(1)
    {
        printf("输入数列长度：");
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        int l=1,r=1;
        int sum=calc(1,n,l,r);
        if(sum>0)
        {
            cout<<"最大子段和:"<<sum<<endl;
            cout<<"起点和终点:"<<l<<" "<<r<<endl;
        }
        else
        {
            cout<<"最大子段和:"<<sum<<endl;
            cout<<"无起点和终点！"<<endl;
        }
        cout<<endl;
    }
    return 0;
}