9. Largest Sum Contiguous Subarray (Kadane's Algorithm)

Given an array of integers (which may include negatives), find the maximum possible sum of any contiguous subarray. Print that sum.

Input: The first line contains an integer n. The second line contains n space-separated integers, each between -10^4 and 10^4. Output: Print a single integer - the maximum sum of any contiguous subarray.

1 <= n <= 10^5, -10^4 <= arr[i] <= 10^4

If every single element is negative, Kadane's algorithm still works correctly as long as you don't force 'current' to reset to 0 - the answer becomes the largest (least negative) single element, which the max() comparison naturally produces.

Find the contiguous stretch of an array (which may contain negative numbers) that adds up to the biggest possible sum. Brute force: Check every possible contiguous subarray directly (two nested loops, or three with a naive sum recomputation) and track the best total - this costs O(n²) or O(n³), too slow once n grows large. Optimised: Kadane's insight is that a running 'best sum ending exactly here' only ever needs ONE decision at each step - extend the previous run, or restart from here - because any negative running total can only ever HURT a future sum, so it's never worth carrying forward. This turns an all-pairs search into a single O(n) linear scan.

Consider every possible subarray by choosing a start index i and an end index j >= i, and for each pair recompute the sum of arr[i..j] by adding up its elements one by one in an inner loop, keeping track of the best sum seen. This checks literally every contiguous subarray so it's certainly correct, but recomputing each subarray's sum from scratch means a huge amount of repeated addition work. Time: O(n^3) Space: O(1)

Make a single pass while maintaining a running sum of the best subarray ending at the current position: at each element, either extend the previous running subarray by adding the current element, or start fresh from the current element alone, whichever gives a larger sum, and track the best such running sum seen anywhere. This works because a subarray with a negative running sum can never help extend a better subarray beyond it, so it's always safe to reset there, letting the whole array be scanned just once. Time: O(n) Space: O(1)

Precompute a prefix sum array in one pass, where prefix[i] holds the sum of all elements up to index i. Then for every pair (i, j), the sum of the subarray between them can be looked up in O(1) as prefix[j] - prefix[i-1] instead of re-adding elements, so the nested loop over all pairs no longer needs an inner summation loop. This removes the innermost loop of the brute-force approach entirely, though it's still checking every one of the O(n^2) possible subarrays. Time: O(n^2) Space: O(n)

1. Walk through the array once, keeping two running values: 'best sum ending exactly here' and 'best sum seen anywhere so far'. 2. At each element, decide: either extend the previous running stretch by adding this element, OR abandon the previous stretch and start fresh from this element alone - whichever gives a bigger sum. 3. Update the overall best-seen-anywhere value whenever the current running stretch beats it.

Time: O(n) - one single pass through the array. Space: O(1) - just two running trackers regardless of array size.

n = 1 (the answer is that single element, whether positive or negative); an array where every element is negative (the answer is the largest single element, not zero); and n = 10^5 (largest, confirming Kadane's O(n) approach).

This is one of the most famous, most-asked array problems in all of technical interviewing - be ready to instantly recite the recurrence (current = max(arr[i], current + arr[i])) and to explain the all-negative edge case confidently.