1012 - Maximum Sum

Time Limit: 15s Memory Limit: 128MB

Submissions: 1138 Solved: 59
Description
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example, 4, 2, 1, 5, 3 in this subsequence a few possible increasing subsequences are 1) 4 2) 2 3) 1 4) 5 5) 3 6) 4, 5 7) 2, 5 8) 2, 3 9) 1, 5 10) 1, 3 but 4, 5 gievs the maximum sum. Your task is how to find such the maximum sum in a given integer array.
Input
Multiply Cases, For each case: The first line contains N(0< N <=1000000), which is the number of the integer array. The second line contains N integer numbers not exceeding 2000000 by the absolute value.
Output
For each case, output only one integer, which is the maximum sum of increasing subsequences.
Sample Input
5
4 2 1 5 3
Sample Output
9
Hint
Source
ACman