Largest Sum Decreasing Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Given a sequence, find a strictly decreasing subsequence with the maximum possible sum and print that sum.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Greedy, Brute force
Solved: No attempts yet

Problem

Given a sequence A, write a program that finds the decreasing subsequence of A with the largest sum.

For example, if A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}, the decreasing subsequence with the largest sum is A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5}, and its sum is 186.

Input

The first line contains N, the size of sequence A (1 ≤ N ≤ 1000).

The second line contains the elements Ai of sequence A (1 ≤ Ai ≤ 1,000).

Output

Print the sum of the decreasing subsequence of A with the largest sum.

Examples1

Example 1
Input
```
10
1 100 2 50 60 8 7 3 6 5
```
Expected output
```
186
```