即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

51nod 2级算法题-1050

编程语言 lengqiu2015 15℃ 0评论
本文目录
[隐藏]

1.1050 循环数组最大子段和

基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题

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。

1.1.Input

第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N+1行:N个整数 (-10^9 <= S[i] <= 10^9)

1.2.Output

输出循环数组的最大子段和。

1.3.Input示例

6
-2
11
-4
13
-5
-2

1.4.Output示例

20

两种情况,看有没有跨过首尾。没有跨首尾的情况简单;当考虑跨过首尾的时候,直接将数组和减掉中间一段负的最多的时候,这里直接将数组取负后求最大子段和,比较大小就好!

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define endl "\n"

const long long maxn=50000+100;
long long a[maxn];
int main(){
    long long n;
    cin>>n;
    long long x=0;
    long long ans=0;
    for(long long i=0;icin>>a[i];
        ans+=a[i];
    }
    long long sum=0;
    long long Max=0;
    for(long long i=0;iif(sum<0){
            sum=0;
        }
        if(sum>Max){
            Max=sum;
        }
    }
    for(long long i=0;i1;
    }
    long long Min=0;
    sum=0;
    for(long long i=0;iif(sum<0){
            sum=0;
        }
        if(sum>Min){
            Min=sum;
        }
    }
    if((ans+Min)>Max){
        Max=ans+Min;
    }
    cout<return 0;
}

转载请注明:CodingBlog » 51nod 2级算法题-1050

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情