Maximum Subarray

Problem Statement

Given an array of integers arr, find the contiguous subarray (containing at least one element) that has the highest sum and return that sum.

Examples

Example 1:
Input: [3, -2, 5, -1, 6, -3]
Output: 10
Explanation: The subarray [3, -2, 5, -1, 6] has the maximum sum of 10.

Example 2:
Input: [-4, -1, -7, -3]
Output: -1
Explanation: The maximum sum is -1 from the subarray [-1].

Example 3:
Input: [2, 1, -5, 4, -2, 3]
Output: 5
Explanation: The subarray [4, -2, 3] has the largest sum, which is 5.
    

Constraints

• 1 ≤ length of arr ≤ 2 × 10⁴
• -10⁵ ≤ arr[i] ≤ 10⁵