Maximum Subarray Sum (Kadane's Algorithm)

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and then return its sum.

Formally, given an array \(a_1, a_2, \ldots, a_n\), compute:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\)

You are expected to use Kadane's algorithm to achieve a time complexity of \(O(n)\) and constant \(O(1)\) extra space.

inputFormat

The first line of input contains an integer (N) which denotes the number of elements in the array. The second line contains (N) space-separated integers. If (N = 0), the array is considered empty.

outputFormat

Output a single integer which is the sum of the maximum contiguous subarray.## sample

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

6