Maximum Subarray Sum Problem Statement

Given an array of integers, determine the maximum possible sum of any contiguous subarray within the array.

Example:

Input:

array = [34, -50, 42, 14, -5, 86]

Output:

137

Explanation:

The maximum sum is achieved by the subarray [42, 14, -5, 86].

Input:

array = [-5, -1, -8, -9]

Output:

-1

Explanation:

The maximum sum is -1, achieved by the subarray [-1].

Constraints:

• 1 ≤ N ≤ 106, where N is the number of elements in the array.
• -104 ≤ array[i] ≤ 104

Note:

The solution should have a time complexity of O(N).

Input:

The first line contains a single integer, N, the size of the array. The second line contains N space-separated integers representing the elements of the array.

Output:

A single integer, the maximum subarray sum.