poj 2479 Maximum sum(递推)
2024-09-29 14:42:26
题意:给定n个数,求两段连续不重叠子段的最大和。
思路非常easy。把原串划为两段。求两段的连续最大子串和之和,这里要先预处理一下,用lmax数组表示1到i的最大连续子串和,用rmax数组表示n到i的最大连续子串和,这样将时间复杂度降为O(n)。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std; const int maxn = 50000 + 50;
const int INF = 0x3f3f3f3f;
int n, a[maxn], lmax[maxn], rmax[maxn]; void init() {
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int enda = a[1];
lmax[1] = a[1];
for(int i = 2; i <= n; i++) {
enda = max(enda+a[i], a[i]);
lmax[i] = max(lmax[i-1], enda);
}
enda = a[n];
rmax[n] = a[n];
for(int i = n-1; i >= 1; i--) {
enda = max(enda+a[i], a[i]);
rmax[i] = max(rmax[i+1], enda);
}
} void solve() {
int ans = -INF;
for(int i = 1; i < n; i++) ans = max(ans, lmax[i]+rmax[i+1]);
cout << ans << endl;
} int main() {
//freopen("input.txt", "r", stdin);
int t; cin >> t;
while(t--) {
init();
solve();
}
return 0;
}
最新文章
- c语言中(*p)[n]和*p[n]的区别
- [leetcode 34] search for a range
- Android EditText输入最大值提示功能
- iOS 一个工程中引用其他工程时编译的Architecture问题
- 设计模式-观察者模式(Observer)
- tomcat manager app 和 host maganger
- MSSQL复制功能实现与Oracle数据库同步
- Session里的对象是不可靠的!
- MySQL数据库改名字
- 常用WebService收集
- 包含中文字符的NSString 转换为NSURL
- migo的增强
- Java基础系列--冒泡排序
- knockoutjs data-bind 声明式绑定整理
- Solr 07 - Solr从MySQL数据库中导入数据 (Solr DIH的使用示例)
- C语言博客作业6---结构体&;文件
- 【进阶1-5期】JavaScript深入之4类常见内存泄漏及如何避免(转)
- Solution for unable to create ";dead-letter-exchange"; in RabbitMQ
- oracle查询所有初始化参数(含隐含参数)
- Linux进程调度的运行队列
热门文章
- 【bzoj4999】This Problem Is Too Simple! 树链剖分+动态开点线段树
- webstorm配置autoprefix
- mac python 安装参考
- RocketMq使用注意事项
- 洛谷P1135 奇怪的电梯
- [CODEVS1205]单词反转
- C# Log日志工具类
- dva脚手架 dva-cli 配置roadhogrc,antd-mobile样式按需加载 不生效的问题
- [LeetCode] Balanced Binary Tree 深度搜索
- Swift Perfect 服务器配置(Ubuntu16.0.4 主机、虚拟机)