1589: 【基础】最大子段和
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：141
解决：45
题目描述
有n个整数，排成一排，例如: n=7
-2 13 12 9 14 -10 2 （7个整数）
其最大的部分和为 48 （即 13+12+9+14）
-2 13 12 9 14 -10 2 （7个整数）
其最大的部分和为 48 （即 13+12+9+14）
输入
第一行一个整数 n(1≤n≤2*105)
第二行n个整数（-104≤xi≤104）
数之间有一个空格；其中xi有正数
第二行n个整数（-104≤xi≤104）
数之间有一个空格；其中xi有正数
输出
一个整数（即最大的连续的部分和）
样例输入 复制
7
-2 13 12 9 14 -10 2 样例输出 复制
48提示
样例2：
输入：
7
2 -4 3 -1 2 -4 3
输出：
4
【来源】
2014江苏省青少年信息学奥林匹克竞赛复赛
方法：前缀和、DP、地推、单调队列
同样题目：https://www.luogu.com.cn/problem/P1115?contestId=136595
输入：
7
2 -4 3 -1 2 -4 3
输出：
4
【来源】
2014江苏省青少年信息学奥林匹克竞赛复赛
方法：前缀和、DP、地推、单调队列
同样题目：https://www.luogu.com.cn/problem/P1115?contestId=136595