循环数组最大子段和

傷城~ 2022-06-12 12:07 199阅读 0赞

N个整数组成的循环序列a 1 1,a 2 2,a 3 3,…,a n n，求该序列如a i i\+a i\+1 i+1\+…+a j j的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a n−1 n−1,a n n,a 1 1,a 2 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 i <= 10^9)

Output

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

Sample Input

6
    -2
    11
    -4
    13
    -5
    -2

Sample Output

20

思路：如果最大值不是在断点处取得的话，那就是和求普通的最大子序列和；如果是最大值是在断点处取得，那就特殊的处理它

#include<cstdio>
    #include<algorithm>
    using namespace std;
    int main()
    {
        int n,x,ok;
        long long sum,s,m,minsum,maxsum;
        while(scanf("%d",&n)!=EOF)
        {
            ok=0;
            scanf("%d",&x);
            if(x>0)
                ok=1;
            sum=s=m=minsum=maxsum=x;
            while(--n)
            {
                scanf("%d",&x);
                if(x>0)
                ok=1;
                sum+=x;
                if(s<0)
                    s+=x;
                else
                    s=x;
                minsum=min(s,minsum);
                if(m>0)
                    m+=x;
                else
                    m=x;
                maxsum=max(m,maxsum);
            }
            maxsum=max(maxsum,sum-minsum);//sum-minsum是特殊处理
            if(ok)
                printf("%lld\n",maxsum);
            else
                printf("0\n");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子段和问题

最大子段和问题描述给定由n个整数(可能为负整数)组成的序列a1，a2， a3… ， an，寻找它的某个连续子段，使得其和最大。例如( -2,11,-4,13,

妖狐艹你老母/ 2024年03月17日 09:53/ 0 赞/ 63 阅读

相关 51nod1050 循环数组最大子段和 dp

N个整数组成的循环序列a\[1\],a\[2\],a\[3\],…,a\[n\]，求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的连续的子段和的最大值（循环序列是指

谁借莪１个温暖的怀抱￠/ 2024年02月17日 19:20/ 0 赞/ 71 阅读

相关最大子段和问题

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11

心已赠人/ 2023年10月05日 13:29/ 0 赞/ 38 阅读

相关 P1115-最大子段和

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

不念不忘少年蓝@/ 2023年06月01日 08:49/ 0 赞/ 15 阅读

相关 POJ 1050 最大子段和的延伸最大子矩阵

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。 j

野性酷女/ 2022年09月30日 03:46/ 0 赞/ 171 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 200 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 208 阅读

相关循环数组最大子段和

N个整数组成的循环序列a 1 1,a 2 2,a 3 3,…,a n n，求该序列如a i i\+a i\+1 i+1\+…+a j j的连续的子段和的最大值（循环序列是指n个

傷城~/ 2022年06月12日 12:07/ 0 赞/ 200 阅读

相关最大和子数组

1、任务要求给你一个数组，里面的元素为正整数、负整数、零，请你输出这个数组的一段，我们成为最大和子数组，子数组满足它的所有元素之和是原数组中最大的。即原数组中不存在另一

叁歲伎倆/ 2022年05月21日 06:25/ 0 赞/ 185 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 251 阅读