1012 - Maximum Sum
Time Limit : 15 Second
Memory Limit : 128 MB
Submission: 1247
Solved: 71
- 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