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$$
4 5 -2 7 -3
17
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$$
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor