Greedy on Contiguous Subarrays

Problem Representative task for this round: greedy optimization over contiguous subarrays — e.g. find the contiguous subarray with the maximum sum (values may be negative). The optimal approach is required directly; brute-force enumeration is not accepted.

Input / Output

• Input: int array nums (may contain negatives).
• Output: the maximum subarray sum (and/or the subarray bounds).

Constraints

• n up to 10^5 — O(n) expected; O(n^2) subarray enumeration is explicitly rejected.

Example

• nums = [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1]).