Maximum Sum Subarray Problem Statement

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

Example:

Input:

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

Output:

137

Explanation:

The maximum sum of a contiguous subarray is 137, which is the sum of the elements [42, 14, -5, 86].

Input:

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

Output:

-1

Explanation:

The maximum sum of a contiguous subarray is -1, as choosing any subarray cannot yield a greater sum.

Input:

N
array of N space-separated integers

Output:

Maximum sum of any contiguous subarray

Constraints:

• 1 ≤ N ≤ 10⁵
• -10⁴ ≤ array[i] ≤ 10⁴

Note:

The solution should be accomplished in O(N) time complexity.