Maximum Subarray Sum Problem Statement

Given an array of numbers, the task is to find the maximum sum of any contiguous subarray of the array.

Input:

The first line of input contains the size of the array, denoted by N. The second line contains N space-separated integers representing the array elements.

Output:

The first and only line of output should print the maximum subarray sum.

Example:

Input:

6
34 -50 42 14 -5 86

Output:

137

Explanation:

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

Input:

4
-5 -1 -8 -9

Output:

-1

Explanation:

The maximum sum is -1, which is just the largest number in this case.

Constraints:

• The solution should be implemented in O(N) time.
• N can be large, so efficient solutions are favorable.

Note:

Consider edge cases such as all numbers being negative.