Arrays And Strings
Kadane Algorithm
Track the best subarray ending at each index and keep the maximum subarray seen so far.
O(n) time / O(1) space
best sum: 5running sum: 5
Index 0L/R
5Index 1
5Index 2
5Index 3
6Index 4
8Index 5
11Time
O(n)
Space
O(1)
Step Note
Start with 5 as both current and best subarray sum.
function maxSubarray(values: number[]) {
let current = values[0]
let best = values[0]
for (let index = 1; index < values.length; index++) {
current = Math.max(values[index], current + values[index])
best = Math.max(best, current)
}
return best
}