Description
Learn, learn and learn again — Valera has to do this every day. He is studying at mathematical school, where math is the main discipline. The mathematics teacher loves her discipline very much and tries to cultivate this love in children. That's why she always gives her students large and difficult homework. Despite that Valera is one of the best students, he failed to manage with the new homework. That's why he asks for your help. He has the following task. A sequence of n numbers is given. A prefix of a sequence is the part of the sequence (possibly empty), taken from the start of the sequence. A suffix of a sequence is the part of the sequence (possibly empty), taken from the end of the sequence. It is allowed to sequentially make two operations with the sequence. The first operation is to take some prefix of the sequence and multiply all numbers in this prefix by - 1. The second operation is to take some suffix and multiply all numbers in it by - 1. The chosen prefix and suffix may intersect. What is the maximum total sum of the sequence that can be obtained by applying the described operations?
Input
The first line contains integer n (1 ≤ n ≤ 105) — amount of elements in the sequence. The second line contains n integers ai ( - 104 ≤ ai ≤ 104) — the sequence itself.
Output
The first and the only line of the output should contain the answer to the problem.
Sample Input
3 -1 -2 -3
6
5 -4 2 0 5 0
11
5 -1 10 -5 10 -2
18
题意:
将某段前缀和某段后缀同时乘以-1或者不乘,使整个数列和达到最大值。
思路:
寻找数列中的最大子序列正数和(尽可能的找到一个最大的正数和,没有就为0,与最大子序列和有区别,区别在于子序列和可以为负数)max,未改变序列符号前的总和为sum,则需要改变符号部分的和为sum-max,改变符号后为max-sum,最后将最大子序列正数和max 与 改变符号部分和max-sum相加,那么得出来的数就是所要求的最大值 2*max-sum。
AC:
#include<stdio.h> int main() { int N,i,number[100005],sum=0,max=0,sum1=0; scanf("%d",&N); for(i=0;i<N;i++) { scanf("%d",&number[i]); sum+=number[i]; //为改变符号时候的总和 } for(i=0;i<N;i++) { sum1+=number[i]; if(sum1<0) sum1=0; //如果算到此时的和为小于0的数,则重新开始计算 //这里是用sum1来比较是否小于0 //一开始写的时候是if(number[i]<0) continue; //因为单纯只以为这是忽略序列前缀小于0的操作,如果后面有在正数之间存在负数,则也会被continue掉 //那么单纯用number[i]来判断是否小于0的话,意思就是说,凡是小于0的数都不加上去,加上去的都是整数 //那么得出来的数不是代表最大连续子序列正数和,而是序列的正数和 if(sum1>max) max=sum1; //如果和不小于0的话,那就是一个正数,每次得出来的正数和与max比较 //循环结束后就会得到最大连续子序列正数和了 } //max为最大连续子序列正数和 printf("%d\n",2*max-sum); return 0; }
Why:(Details in“最大连续子序列正数和求法”)
for(i=0;i<N;i++) { sum1+=number[i]; if(sum1<0) sum1=0; if(sum1>max) max=sum1; }
为什么不能写成这样:
i=0; while(number[i]<0) i++; //先忽略前面的负数项,从正数项开始求 for(i;i<N;i++) { sum1+=number[i]; if(sum1>max) max=sum1; }
Improve:
参考别人的写法,发现可以把代码写得更加简短。
#include<stdio.h> int main() { int N,i,sum=0,number,max=0,summax=0; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&number); sum+=number;//求原来的和 summax+=number;//求最大子序列和 if(summax<0) summax=0; if(summax>max) max=summax; //只要summax不小于0,那就不会进行清0操作 //summax只要大于0都会继续相加,无论number是正还是负,因为下面还会有比较操作,所以number操作不影响最大值 //模拟max[i]=max[i-1]>=0?max[i-1]+number[i]:number[i]的过程 //如果max[i-1]小于0则令max[i-1]=0,循环结束到下一项就是max[i]+=number[i] //如果max[i-1]大于等于0,则继续叠加,循环结束后就是max[i]=max[i-1]+number[i]; } printf("%d\n",2*max-sum); } //不需要开个数组来保存数据,直接输入一个数就加和一个数,判断一个数
总结:
理解很多次才把题目给理解了……一开始以为是前缀和后缀的数量是一样的,思考了很久才发现一直都理解错了。既然前缀和后缀改变符号的数量是任意的,通过改变或者不改变来使整个序列和达到最大值。再进一步思考,为什么要改变这个这个前缀和后缀呢,是因为这些要改变的这些数全部加起来是个负数,在原本已经是“最大连续子序列正数和”的基础上再加上这些“前缀和后缀”的话,那就会使这个子序列和减少了。所以要增加这个最大连续子序列正数和的话,就要将这些前缀和后缀变成正数,所以就要乘以-1,再加上这个序列的最大连续子序列正数和来求得这整个数列的最大值。
既然这样,那问题就转化为求这个序列的最大连续子序列正数和了。虽然想到了这一步,但是代码实现方面还是很弱,发现了自己写的代码为什么不对,为什么要那样写才可以求出最大子序列。理解了之后又可以进一步的优化代码,不需要开数组来存储数据,而且也只需要循环一次数组就可以了。
相关推荐
用于施工安全设施计算,施工方案,技术交底,应急预案、可以计算模板支架体系,高支模,地基承载力,边坡承载力,卸料平台安全计算等,网络收集,请支持正版
linux 流程图工具,可以选择语言, 类图,uml, 免费版,可以用 linux 流程图工具,可以选择语言, 类图,uml, 免费版,可以用
autoitV3.2.13.7 版本,提供下载,汉化版本包括帮助文档
xcode真机 13.7.zip
Location-cleaned13.7.rar
北京鼎汉通技术有限公司无线测温说明书_13.7.10.doc
绘图软件、Draw.io-13.7.9、.drawio文件格式
高中物理 13.7.8 光的颜色 色散 激光课件 新人教选修34 .ppt
opencv2版本以上,需要额外编译所需要的文件,该版本为opencv-2.4.13.7,没有opencv_contrib版本。
朋友圈广告助手最新版13.7.0需要最新版请看安装说明,支持二次开发,有需要的可以联系
可上传下载。作网站必备。FlashFXPV3.8Beta13.7.9Build1348烈火汉化绿色版功能强大FXP FTP工具绿色版
资源分类:Python库 所属语言:Python 资源全名:pyginx-0.1.13.7.7-cp36-cp36m-macosx_10_13_x86_64.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
SDK 13.7
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...
DeviceSupport 13.7
2012年最新最快的web服务器nginx下载,linux版本