All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?