博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
题目1011:最大连续子序列 O(n)
阅读量:6490 次
发布时间:2019-06-24

本文共 979 字,大约阅读时间需要 3 分钟。

题目大意:给出一系列的数字。要求你输出这些数字的最大连续和,并输出构成这个最大连续和的第一个数和最后一个数

解题思路:用一个变量维护最大连续和

假设当前这个变量小于0的话,就表示这个变量仅仅会拉低连续和的值了。所以将其变为0
假设当前这个变量大于0。不管它多小,最大连续和加上它都仅仅会增大而不会减小,所以不用改变这个变量
假设当前变量是0的话,就要依据题目来更新了

#include
#include
const int N = 10010;int num[N];int n, ans_l, ans_r, ans_Max;void solve() { int Max = num[0], Sum = num[0]; int l, r; l = r = ans_l = ans_r = 0; ans_Max = Max; for(int i = 1; i < n; i++) { if(Sum < 0) { Sum = 0; l = r = i; } Sum += num[i]; r = i; if(Sum > Max) { ans_r = r; ans_l = l; Max = Sum; ans_Max = Max; } }}int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 0; i < n; i++) scanf("%d", &num[i]); solve(); if(ans_Max >= 0) printf("%d %d %d\n", ans_Max, num[ans_l], num[ans_r]); else printf("0 %d %d\n", num[0], num[n - 1]); } return 0;}

转载地址:http://mneuo.baihongyu.com/

你可能感兴趣的文章
你不是真的想要100万-转
查看>>
绕开Live SDK内存释放bug和实现延迟自动刷新
查看>>
C#下载文件(可显示进度)的方法实现
查看>>
艾伟_转载:在PC上显示和操作Windows Mobile
查看>>
艾伟也谈项目管理,有一种企业文化叫产品精神
查看>>
艾伟也谈项目管理,如何管理“人”
查看>>
int main(int argc,char** argv)参数的意义
查看>>
ArrayList与LinkedList的区别
查看>>
Storm拓扑的并行度(parallelism)介绍
查看>>
性能测试知多少---性能分析与调优的原理
查看>>
put()
查看>>
coretext简单使用
查看>>
Ext.grid.panel 改变某一行的字体颜色
查看>>
获取Linux磁盘分区的UUID
查看>>
Tomcat在Linux的配置
查看>>
WIN8 默认以管理员启动程序
查看>>
Mongo数据两表关联创建视图示例
查看>>
spring-boot (三) spring data jpa
查看>>
【Maximal Rectangle】cpp
查看>>
命令行方式运行yii2程序
查看>>