Maximum Subarray Sum and the Subarray Itself (Kadane's Algorithm)

Problem: Given an array of integers, find the maximum possible sum of a contiguous subarray, and additionally return the subarray itself (not just the sum).

Constraints: Array may contain negative numbers.

Example: [-2,1,-3,4,-1,2,1,-5,4] -> max sum = 6, subarray = [4,-1,2,1].

Approach: Kadane's algorithm - maintain a running sum (currentSum) and the best sum seen so far (maxSum); at each element, currentSum = max(element, currentSum + element); update maxSum if currentSum exceeds it. To also return the actual subarray, track the start index whenever currentSum resets to just the current element, and update the best start/end indices whenever maxSum is updated. O(n) time, O(1) space.