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]).

Expected approach

• Kadane's algorithm: best ending here = max(x, bestEndingHere + x); global best = max over positions. O(n) time, O(1) space. Be ready to argue why the greedy/DP choice is safe (a negative running prefix never helps), extend to returning indices, and handle the all-negative array. Related greedy-on-subarray variants to know: max product subarray (track min/max), min-length subarray with sum ≥ target.