Maximum Subarray (Kadane's Algorithm) - Classic Problems | Repovive

CLS22. Maximum Subarray (Kadane's Algorithm)

1s256 MB

Given an array of $n$ integers, find the maximum sum of any contiguous subarray.

A contiguous subarray is a sequence of consecutive elements from the array. The subarray must contain at least one element.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$\text{max\_sum}$

Input

9
-2 1 -3 4 -1 2 1 -5 4

Explanation

For this input, the required output is 6.

Output

Input

5
-5 -2 -8 -1 -3

Explanation

For this input, the required output is -1.

Output

-1

Input

5
1 2 3 4 5

Explanation

For this input, the required output is 15.

Output

Given an array of $n$ integers, find the maximum sum of any contiguous subarray.

A contiguous subarray is a sequence of consecutive elements from the array. The subarray must contain at least one element.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$\text{max\_sum}$