POJ 2593 Max Sequence

Max Sequence

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 17678		Accepted: 7401

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
Give you N integers a1, a2 … aN (|ai| <=1000, 1 <= i <= N). 



You should output S. 

Input

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

40

Source

POJ Monthly–2005.08.28,Li Haoyuan

题解：这个题2479差不多，具体可以看2479的题解，不过感觉这道题的测试数据要比2479弱一些，轻松AC

//主要是刷几道dp练练手

#include 
#include 
#include 

using namespace std;

const int maxn = 1e6+7, inf = -1e9+7;
int a[maxn], ls[maxn], rs[maxn], rst[maxn], s;

int main()
{
    int n;
    while (~scanf("%d", &n) && n)
    {
        for (int i=0; i=0; i--)
            rs[i] = max(rs[i+1]+a[i], a[i]),
            rst[i] = max(rst[i+1], rs[i]);
        for (int i=1; i