Maximum Contiguous Subarray Sum

In this problem, you are given an array of integers representing the power emitted by each stone. Your task is to compute the maximum sum that can be obtained from a contiguous subarray. This is a classic problem that can be solved using Kadane's algorithm.

The recurrence used in Kadane's algorithm is given by: [ dp_i = \max(p_i,; dp_{i-1}+p_i) \quad \text{for } i \ge 1, ] with the initial condition: [ dp_0 = p_0. ]

The final answer is the maximum of all (dp_i) values.

inputFormat

The first line of input contains an integer (n) denoting the number of power stones. The second line contains (n) space-separated integers, where each integer represents the power emitted by the corresponding stone.

outputFormat

Output a single integer representing the maximum sum of power that can be obtained from a contiguous subarray.## sample

5
3 -2 5 -1 4

9