51nod-1050 循环数组最大子段和

发表于 动态规划 分类,标签:

 

N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。
例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。
Input
第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N+1行:N个整数 (-10^9 <= S[i] <= 10^9)
Output
输出循环数组的最大子段和。
Input示例
6
-2
11
-4
13
-5
-2
Output示例
20



思路:整个数组可以形成一个环,那么最大子段和有两种情况,假设是s[i]和s[j] (i<j),是最大子段和的起点和终点,若s[i]是起点,s[j]是终点,那么跟一般的求数组的最大子段和一样,若s[j]是起点,s[i]是终点,那么以s[i]为起点,s[j]为终点的一段就是最小子段和。

所以:分别求出这个数组的最大子段和跟这个数组的和-(减)最小子段和,然后比较,较大的就是这个循环数组的最大子段和。


代码:

#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include <string.h>
#define LL long long
#define MAX 1e9
using namespace std;
int main()
{
    int n;
    LL maxx,minn,sum,k;
    scanf("%lld",&n);
    maxx=minn=sum=k=0;
    LL sum_max=0,sum_min=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&k);
        sum+=k;
        sum_max+=k;
        sum_min+=k;
        if(sum_max<0)
            sum_max=0;
        if(sum_min>0)
            sum_min=0;
        if(maxx<sum_max)
            maxx=sum_max;
        if(minn>sum_min)
            minn=sum_min;
    }
    printf("%lld\n",maxx>sum-minn?maxx:(sum-minn));

    return 0;
}


0 篇评论

发表我的评论