P1115 最大子段和(简单DP)
2024-10-07 04:15:59
题目描述
给出一段序列,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个正整数NN,表示了序列的长度。
第二行包含NN个绝对值不大于1000010000的整数A_iAi,描述了这段序列。
输出格式
一个整数,为最大的子段和是多少。子段的最小长度为11。
输入输出样例
输入 #1复制
7
2 -4 3 -1 2 -4 3
输出 #1复制
4
说明/提示
【样例说明】
2,-4,3,-1,2,-4,32,−4,3,−1,2,−4,3中,最大的子段和为4,该子段为3,-1,23,−1,2.
【数据规模与约定】
对于40\%40%的数据,有N ≤ 2000N≤2000。
对于100\%100%的数据,有N ≤ 200000N≤200000。
思路:f[i]表示以i结尾的前i个数字中与第i个数字连续的最大子段和。
如果第i个数字加上f[i-1]变大了,那么f[i]=f[i-1]+a[i];
否则f[i]=a[i];
#include <iostream>
#include<bitset>
#include<string>
using namespace std;
const int maxn= ;
long long f[maxn];
long long a[maxn];
int main()
{
int n;
cin >> n;
for(int i=;i<=n;i++)
cin >> a[i];
f[]=a[];
long long ans=-1e18;
for(int i=;i<=n;i++)
{
f[i]=max(a[i],f[i-]+a[i]);
ans=max(ans,f[i]);
}
cout << ans << endl;
return ;
}
最新文章
- asp.net和js读取文件的MD5值的方法
- 使用 Date 和 SimpleDateFormat 类表示时间、Calendar类和Math类
- Debian配置Apache2支持mod-python和cgi模块
- 百度Map与HT for Web结合的GIS网络拓扑应用
- HDU 1506 Largest Rectangle in a Histogram (dp左右处理边界的矩形问题)
- MVC中Asp.Net管道(二)
- HTTP 错误 500.19 - Internal Server Error
- ubuntu zend-eclipse-php debugger调试
- UVA - 11346 Probability (概率)
- pip 错误Requested **, but installing version **
- contentProvider内容提供者
- JSP自定义标签——传统标签
- FFmpeg的Android平台移植—编译篇
- JWT
- centos7通过nginx搭建SSL
- solr+zookeeper集群配置
- hdoj:2023
- Unity3D避免代码被反编译
- 3 TensorFlow入门之识别手写数字
- requestAnimationFrame 的实验性实践