Maximum Subarray Sum Problem Statement

Given an array 'ARR' of integers with length 'N', the task is to determine the sum of the subarray (including an empty subarray) that yields the maximum sum among all possible subarrays.

Explanation:

A subarray is a contiguous segment of an array. In other words, it can be created by removing zero or more elements from the beginning and zero or more elements from the end of the array.

Input:

N
ARR[0] ARR[1] ... ARR[N-1]

Output:

Maximum subarray sum

Example:

If given:

N = 5
ARR = [-2, 1, -3, 4, -1]

Output would be:

4

As the subarray [4] produces the maximum sum of 4.

Constraints:

• 1 <= N <= 10^6
• -10^6 <= A[i] <= 10^6, where A[i] denotes the elements of the array.

Note:

The sum of an empty subarray is considered to be 0.