循环数组最大子段和

傷城~ 2022-06-12 12:07 161阅读 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 条评论，161人围观）

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

相关阅读

相关最大子段和问题

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

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

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

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

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

相关最大子段和

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

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

相关最大子段和

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

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

相关最大子段和动态规划实现

找到《最大子段和问题的动态规划求解》的pdf，讲解很透彻。 public class Main { public static void ma

偏执的太偏执、/ 2022年06月18日 11:08/ 0 赞/ 206 阅读

相关循环数组最大子段和

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 赞/ 162 阅读

相关数据结构：最大子段和问题

最大字段和问题是这样的，在一个给定的数组中寻找子数组之和的最大值，暴力肯定是超时的，这个是个典型的动态规划DP 不过下面的做法还有点不恰当，当所有的元素都是负数的时候

今天药忘吃喽~/ 2022年05月31日 12:51/ 0 赞/ 155 阅读

相关最大和子数组

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

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

相关最大子段和

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

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

相关最大子数组

/\求子数组的最大和题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的

一时失言乱红尘/ 2022年01月06日 13:49/ 0 赞/ 265 阅读