POJ2479(最长连续子序列和)
2024-08-31 12:57:42
Maximum sum
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 37035 | Accepted: 11551 |
Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample Input
1 10
1 -1 2 2 3 -3 4 -4 5 -5
Sample Output
13
Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.
Source
POJ Contest,Author:Mathematica@ZSU
题意:原串分成两个不相交连续子序列,求最大和
const int maxn = ; int num[maxn];
int le[maxn], ri[maxn]; int main() { int T;
scanf("%d", &T);
while (T --) {
memset(le, , sizeof(le));
memset(ri, , sizeof(ri));
int n;
scanf("%d", &n);
for (int i = ; i <= n; i ++) scanf("%d", &num[i]);
le[] = num[];
ri[n] = num[n];
int cur_sum = num[] < ? : num[];
for (int i = ; i <= n; i ++) {
cur_sum += num[i];
le[i] = max(le[i-], cur_sum);
if (cur_sum < ) cur_sum = ;
}
cur_sum = num[n] < ? : num[n];
for (int i = n - ; i >= ; i --) {
cur_sum += num[i];
ri[i] = max(ri[i+], cur_sum);
if (cur_sum < ) cur_sum = ;
}
int ans = -0x3fffffff;
for (int i = ; i <= n; i ++) {
ans = max(ans, le[i-] + ri[i]);
}
printf("%d\n", ans);
} return ;
}
最新文章
- 三步将Node应用部署到Heroku上
- [综]隐马尔可夫模型Hidden Markov Model (HMM)
- JavaScript-cookie是客户端本地,持久存储用户私密数据的文件
- SharePoint 2013 REST 服务使用简介
- HTML5学习总结-08 WebSocket 服务器推送
- Ranorex入门指南
- Node.js +Express+MongoDB+mogoose+ejs+bootstrap+jquery
- ";System.Web"; 中不存在类型或命名空间
- iOS 10推送通知开发
- MySQL字符串相关函数学习一
- js中的伪数组
- Leetcode_13_Roman to Integer
- Tensorflow基本操作理解
- PhysicalBasedRendering(一)物理篇
- 用户认证--------------auth模块
- Linux重启服务器步骤
- SQLSERVER 2008 技术内幕 T-SQL查询 笔记1: SQL 执行顺序
- 一点ExtJS开发的感悟
- 新浪微博API使用初步介绍——解决回调地址的问题
- React读取Excel——js-xlsx 插件的使用
热门文章
- QC的使用学习(二)
- Struts2(五.用户注册的实现及整合Action的配置方法)
- JavaScript 面向对象 原型(prototype) 继承
- C# Lambda表达式使用累加器例子
- lintcode-95-验证二叉查找树
- requests快速入门
- spring MVC 字符串数组传值 字符带有逗号,问题
- [剑指Offer] 36.两个链表的第一个公共结点
- [剑指Offer] 21.栈的压入、弹出序列
- 对于response.setContentType(MIME)的解释