Kadane's Algorithm
Imagine it is 1977. You do not have a degree in computer science. You have not spent months grinding leetcode. You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum. The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...