AC日记——最大子段和 洛谷 P1115
2024-09-05 06:40:58
题目描述
给出一段序列,选出其中连续且非空的一段使得这段和最大。
输入输出格式
输入格式:
输入文件maxsum1.in的第一行是一个正整数N,表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i],描述了这段序列。
输出格式:
输入文件maxsum1.out仅包括1个整数,为最大的子段和是多少。子段的最小长度为1。
输入输出样例
输入样例#1:
7
2 -4 3 -1 2 -4 3
输出样例#1:
4
说明
【样例说明】2 -4 3 -1 2 -4 3
【数据规模与约定】
对于40%的数据,有N ≤ 2000。
对于100%的数据,有N ≤ 200000。
思路:
水题使我快乐;
dp[i][3];
i表示当前在序列中的位置;
j=2,表示当前位置及以前出现的最大值;
j=1,表示,当前位置的最大值;
j=0,表示,序列中第i个数;
方程见代码;
来,上代码:
#include <cstdio>
#include <iostream> using namespace std; int if_z,n,dp[][],ans; char Cget; inline void in(int &now)
{
now=,if_z=,Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} int main()
{
in(n);dp[][]=dp[][]=-0x7ffffff;
for(int i=;i<=n;i++)
{
in(dp[i][]);
dp[i][]=max(dp[i][],dp[i-][]+dp[i][]);
dp[i][]=max(dp[i-][],dp[i][]);
}
cout<<dp[n][];
return ;
}
最新文章
- VR的世界里没有雾霾!暴风魔镜发布Matrix一体机
- [ javascript canvas 插件演示 ] canvas 插件演示
- C+命令行+方向键=简易版扫雷
- CF 371C-Hamburgers[二分答案]
- 证明N={1,2,...,n,...}最高万元 黄晓宁
- mysql版本,根据经纬度定位排序sql
- LKD: Chapter 5 System Call
- Mysql学习路线
- VS2017 启动调试出现 无法启动程序“http://localhost:15613” 操作在当前状态中是非法的。 同时附加进程也是错误的解决方法
- 薛兆丰吴军何帆曾鸣万维刚李笑来罗永浩等得到APP专栏作者的书23本
- 【JS】for in循环对象,hasOwnProperty()的作用
- 【代码笔记】iOS-字符串替换回车和换行
- Oracle 导入单表数据
- sencha touch 在线实战培训 第一期 第一节
- 三步搞定 opencv 初始环境设定
- 告诉你什么是javascript的回调函数
- hasura graphql-engine v1.0.0-alpha26 版本新功能
- centos7上使用locate命令
- Typed Arrays in javascripts
- Linux内核学习笔记(6)-- 进程优先级详解(prio、static_prio、normal_prio、rt_priority)
热门文章
- javaEE(4)_response、request对象
- ios之UIButoon
- NSLayoutConstraint.constraintsWithVisualFormat详解,以及AlignAllCenterY
- (32)zabbix分布式监控proxy vs nodes
- C语言之链接库
- Developing
- [WPF自定义控件库]使用WindowChrome的问题
- How To Configure VMware fencing using fence
- [转]构建Python+Selenium2自动化测试环境(二)
- rocketmq 问题