Maximum Sum
/

## Algorithms, Data Structures, Hash Maps, Hash Tables, Sets

Problem
Editorial
Analytics

Given an array $A$ of $N$ integers. Now, you have to output the sum of unique values of the maximum subarray sum of all the possible subarrays of the given array $A$.
Note: Subarray means contiguous elements with atleast one element in it.

Input Format

The first line of the input contains a single integer $N$, the total number of elements in array $A$.
The next line of the input contains $N$ space-separated integers representing the elements of the array.

Output Format

The only single line of the output should contain a single integral value representing the answer to the problem.

Constraints

$1 \le N \le 2000$
$0 \le |A_i| \le 10^9$

SAMPLE INPUT
4
5 -2 7 -3
SAMPLE OUTPUT
17
Explanation

Following are the possible number of subarrays and their respective maximum subarray sums:

$[5] = [5] = 5$
$[5, -2] = [5] = 5$
$[5, -2, 7] = [5, -2, 7] = 10$
$[5, -2, 7, -3] = [5, -2, 7] = 10$
$[-2] = [-2] = -2$
$[-2, 7] = [7] = 7$
$[-2, 7, -3] = [7] = 7$
$[7] = [7] = 7$
$[7, -3] = [7] = 7$
$[-3] = [-3] = -3$

$5 + 10 + (-2) + 7 + (-3) = 17$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...