1004 - Largest Weighted Subsequence

Description

Find the largest weight subsequence of a given sequence of numbers.

• Given a sequence s=<a₁, a₂, ..., a_n>
• A subsequence is s(i,j)=<a_i, a_i+1, ..., a_j>
• Weight w(s(i,j))=a_i + a_i+1 + ... + a_j
• Problem: find the subsequence having largest weight

Example

• Given sequence: -2, 11, -4, 13, -5, 2
• The largest weight subsequence is 11, -4, 13 having weight 20

Input

The first line contains a positive integers N (1 ≤ N ≤ 10⁶).

The second line contains N integers.

Output

You should output on a single line an unique integer that is the maximum value of the sum of the found subsequence.

Sample Input

6
-2, 11, -4, 13, -5, 2

Sample Output

20

Hint

Source

• Submit
• Summary
• Discuss