Largest Sum Increasing Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Pick elements in order so each is larger than the last and their sum is as large as possible.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

You are given a sequence A. Find the increasing subsequence of A whose elements have the largest sum, and print that sum.

A subsequence is what you get by picking some elements of A and keeping their original order. An increasing subsequence is a subsequence whose picked elements grow strictly from left to right. For A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}, picking 1, 2, 50, 60 gives the sum 113, and no increasing subsequence of A has a larger sum.

Input

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

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

Output

Print on the first line the largest sum among the increasing subsequences of A.

Examples3

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