Largest Sum Contiguous Subarray (Kadane)

Problem Given an integer array, find the maximum sum obtainable from a contiguous subarray. The subarray must contain at least one element.

Input / Output

• Input: int array nums (may contain negatives).
• Output: the maximum contiguous subarray sum.

Constraints

• 1 ≤ n ≤ 10^5; values may be negative, so the answer can be negative (an all-negative array).
• O(n) time expected.

Example

• [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1]).
• [-3,-1,-2] → -1 (best is the single largest element).