1050 循環數組最大子段和

原题链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

如果没有循环的条件,那么我们可以用常规的方法算出最大的字段和max1

然后加上循环这个条件,我们可以先求出整个数组的和,然后在求出数组最小子段和,然后然后相减得到max2,然后和ans=max(max1,max2);

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std; 
#define inf -100
#define inf1 100
const int maxn=100;
int a[maxn];
int main()
{
    int n;
    __int64 sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    __int64 flag=a[0];
    __int64 ma=inf;
    for(int i=1;i<n;i++)
    {
        if(flag<0)
        flag=a[i];
        else
        flag+=a[i];
        if(ma<flag)
        ma=flag;
    }
    __int64 mi=inf1;
    flag=a[0];
    for(int i=1;i<n;i++)
    {
        if(flag>0)
        flag=a[i];
        else
        flag+=a[i];
        if(flag<mi) 
        mi=flag;
    }
    __int64 max1=max(sum,sum-mi);
    __int64 ans=max(max1,ma);
    printf("%I64d\n",ans);
}

 

更多相关文章
一周排行