Maximum Sum Subarray Problem Statement

Given an array ARR consisting of N integers, determine the sum of the subarray with the maximum sum, including the possibility of an empty subarray.

A subarray is a contiguous portion of an array and can range from fully (including zero or more elements removed from each end) to partially inclusive of the original array.

Example:

Input:

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

Output:

4

Explanation:

The largest sum subarray is [4] which would give a sum of 4.

Constraints:

• 1 <= N <= 10^6
• -10^6 <= ARR[i] <= 10^6
• Time limit: 1 second