循环数组最大子段和

迈不过友情╰ 2023-07-04 14:14 11阅读 0赞

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 <= Sii <= 10^9)

Output

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

Sample Input

6  
\-2  
11  
\-4  
13  
\-5  
\-2

Sample Output

20

最大子段和：求一个连续子序列的最大值，  
dp\[i\]=max(dp\[i-1\]+a\[i\],a\[i\]) 到a\[i\]的时候看看 a\[i\]+前面的和 与 a\[i\] 本身谁大,取最大值。

本题是循环数组求最大字段和  
两种情况，1.最大子段和在中间段 2.最大子段和在两头

1 就是模板  
2 如果两头是最大子段和，中间就是一个非常负的数，我们把数组取负数，我们依然可以转换成求中间的最大子段和。最后用总和加上取负后的中间最大子段和。

最后结果就是max（1，2）

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    const int inf=0x3f3f3f3f;
    ll a[maxn],dp[maxn];
    ll m1,m2,ma,n;
    ll get_max()
    { 
    	dp[1]=a[1];
    	for(int i=1;i<=n;i++)
    	{ 
    		dp[i]=max(dp[i-1]+a[i],a[i]);
    		ma=max(dp[i],ma);
    	}
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	ll sum=0;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>a[i];
    		sum+=a[i];	
    	}
    	get_max();
    	m1=ma;
    	ma=0; 
    	for(int i=1;i<=n;i++)
    		a[i]*=-1;
    	get_max();
    	m2=ma;
    	cout<<max(m1,m2+sum)<<endl;
    	return 0;
     }

发表评论取消回复

表情：

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

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

相关阅读

相关最大子段和问题

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

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

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

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

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

相关最大子段和问题

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

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

相关循环数组最大子段和

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

迈不过友情╰/ 2023年07月04日 14:14/ 0 赞/ 12 阅读

相关最大连续子数组和（最大子段和）

最大连续子数组和（最大子段和）一、问题描述问题：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a

桃扇骨/ 2023年06月01日 06:23/ 0 赞/ 46 阅读

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

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

比眉伴天荒/ 2022年08月20日 12:28/ 0 赞/ 29 阅读

相关最大子段和

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

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

相关最大子段和

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

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

相关循环数组最大子段和

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

相关最大子段和

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

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