Maximum Subarray Sum Problem Statement

Given an array ARR consisting of N integers, your goal is to determine the maximum possible sum of a non-empty contiguous subarray within this array.

Example of Subarrays:

An array C is considered a subarray of array D if it can be obtained by deleting zero or more elements from the beginning and end of the array D. For instance, for the array [1, 2, 3], all non-empty subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Input:

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

Output:

Print the maximum possible sum of any subarray of the array/list.

Example:

Input:

5
-2 1 -3 4 -1

Output:

4

Explanation:

The subarray [4] has the maximum sum of any contiguous subarray.

Constraints:

• 1 <= N <= 5*105
• -109 <= ARR[i] <= 109
• Time Limit: 1 second

Note:

You do not need to print anything; it has already been taken care of. Implement the required function to find the solution.