Maximum Subarray Sum and the Subarray Itself

Problem Given an array of integers, find the maximum sum achievable by any contiguous subarray, and return the subarray itself rather than only the sum.

Input / Output

• Input: array arr of n integers.
• Output: the maximum contiguous subarray sum, plus the subarray (or its start and end indices).

Constraints

• The array may contain negative numbers, which is what makes the problem non-trivial.
• The subarray must be contiguous and non-empty — so an all-negative array returns its largest single element, not an empty subarray summing to 0.
• Target O(n) time, O(1) extra space.

Example

• [-2,1,-3,4,-1,2,1,-5,4] → max sum 6, subarray [4,-1,2,1]. The -1 is included: a locally bad element is worth absorbing when the surrounding positives outweigh it.
• [-3,-1,-2] → max sum -1, subarray [-1]. This is the case that breaks implementations initialising maxSum to 0.