NYOJ 44 字串和 （最大字串和 线性dp）
2024-09-04 10:04:03
题目链接：
http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=44
子串和
时间限制：5000 ms | 内存限制：65535 KB
难度：3
- 描述
- 给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1<=x<=y<=n。
- 输入
- 第一行是一个整数N(N<=10)表示测试数据的组数）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000) - 输出
- 对于每组测试数据输出和最大的连续子串的和。
- 样例输入
-
1
5
1 2 -1 3 -2 - 样例输出
-
5
- 提示
- 输入数据很多,推荐使用scanf进行输入
-
#include<bits/stdc++.h>
using namespace std;
int f_max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int a[n+];
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int dp[n+];
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
dp[i]=f_max(dp[i-]+a[i],a[i]);
}
int x=dp[];
for(int i=;i<=n;i++)
{
if(x<dp[i])
{
x=dp[i];
}
}
printf("%d\n",x);
}
return ;
}
最新文章
- 响应者链条，如何获取最佳的点击view 以及内部实现
- OpenCascade Tcl vs. ACIS Scheme
- CSS3计数器的使用-遁地龙卷风
- Redis 笔记与总结5 Redis 常用命令之 键值命令 和 服务器命令 && 高级应用之 安全性 和 主从复制
- linux 系统安装 mysql
- POJ2104 k-th number 划分树
- devenv 命令用法
- 执行*.sh脚本时提示Permission denied
- 发布Ubuntu/Linux系统cache，增加可用内存空间
- NFC Spy:基于Android 4.4及以上手机的非接智能卡跟踪仪
- 前端笔记之jQuery（上）加载函数的区别&对象&操作HTML/CSS&动画&选择器
- JavaWeb学习之三层架构实例（二）
- sql server中如何修改视图中的数据？
- H5 CSS的格式
- Python-WEB前端-入门到进阶开发之路
- 潭州课堂25班：Ph201805201 django框架 第九课 模型补充 博客小案例 (课堂笔记)
- 设计服务类网站原型模板分享——Fortyseven
- Java Collection集合方法
- volatile synchronized AtomicInteger的区别
- c++对象的生命周期