Maximum Subarray Sum

Problem Given an integer array that may contain negative numbers, find the contiguous subarray with the largest sum and return that sum.

Input / Output

• Input: an integer array arr with at least one element.
• Output: the maximum sum over all non-empty contiguous subarrays; the extended version also returns the start and end indices.

Constraints

• 1 <= n <= 10^5; values may be negative, zero, or positive.
• The subarray must be non-empty, so an all-negative array returns its largest single element rather than 0.
• Sums can exceed 32-bit range on large inputs — accumulate in 64-bit.

Example

• arr = [-2,1,-3,4,-1,2,1,-5,4] -> 6, from the subarray [4,-1,2,1].
• arr = [-3,-1,-2] -> -1 — the tricky case; initialising best to 0 wrongly returns 0.
• arr = [5] -> 5.