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

2024-01-25 06:20

本文主要是介绍循环数组最大子段和———51nod 1050,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

题目描述:

N个整数组成的循环序列a11,a22,a33,…,ann,求该序列如aii+ai+1i+1+…+ajj的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑an−1n−1,ann,a11,a22这样的序列)。当所给的整数均为负数时和为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

主要思想:

 循环数组最大子段和与常规最大子段和的区别就在于:循环数组比非循环数组多了一种最大子段在截点处两端的情况。

   求L的最小值:对所有元素取负,这样求得-L的最大值,再取负即是L的最小值。最后比较两种情况下求得的最大子段和的值,取最大的就ok了。

代码实现:

#include<stdio.h>
#include<algorithm>
using namespace std;
__int64 a[50005];
__int64 dp[50005];
__int64 d[50005];
__int64 b[50005];
int main(){int n,i;__int64 ans,sum,ais;sum=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%I64d",&a[i]);b[i]=-a[i];//对所有元素取负sum+=a[i];}dp[1]=a[1];ans=a[1];d[1]=b[1];ais=b[1];for(i=1;i<=n;i++){dp[i]=max(dp[i-1]+a[i],a[i]);//常规求d[i]=max(d[i-1]+b[i],b[i]);//最大子段出现在截点两端情况if(dp[i]>ans)ans=dp[i];if(d[i]>ais)ais=d[i];}ans=max(ans,sum+ais);//取最大if(ans<0)printf("0\n");elseprintf("%I64d\n",ans);return 0;
}

 

这篇关于循环数组最大子段和———51nod 1050的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/642336

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for