Medium · Kadane's Algorithm
Understand → Visualise → Practice.
A negative prefix can only hurt every subarray that follows it. Kadane's algorithm decides at each value whether to extend the previous run or start again.
Track `current`, the best sum ending at this index, and `best`, the largest sum seen anywhere.
current = max(value, current + value).
best = max(best, current).
Initialise from nums[0], not zero.
O(n) time and O(1) extra space.
Returning 0 for an all-negative array is wrong; one element must be chosen.
Read the full guides first: Big-O and Complexity, Arrays and Dynamic Arrays, Prefix Sums and Difference Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.