leetcode day 29: max sub array / Kadane’s algorithm

First medium problem, and another IYKNK solution.

Given an array of numbers, search it for the subarray that has the maximum sum, and return the sum.

leetcode rule of thumb: any problem that has a solution with someone’s name on it is not an obvious solution. In this case, it’s Kadane’s method, which is simple but not intuitive enough that one would immediately stumble on it while trying to solve the problem.

A naive solution brute-force sums the subarrays, looking for the best answer; this is O(N^2). Kadane’s algorithm is O(n), which is pretty impressive, and hearkens back to the tree diameter solution: while working on the subproblems, you maintain a global maximum and compare further work to it.

func maxSubArray(nums []int) int {
    localMax := 0
    globalMax := -99999
    for i := 0; i < len(nums); i++ {
        if nums[i] > nums[i] + localMax {
            localMax = nums[i]
        } else {
            localMax = nums[i] + localMax
        }
        if localMax > globalMax {
            globalMax = localMax
        }
    }
    return globalMax
}

We start with a guaranteed-to-be-wrong answer for the global maximum, then start at the beginning of the array. If the next number along is > than the local maximum sum so far, then it’s the new global maximum. Otherwise, add it to the local maximum. If the local maximum is now > the global one, we’ve found a new global max subarray sum, and we save it.

My original version came in disturbingly low in the runtime list, like 5%. I looked at it and said, “this is too simple for me to have gotten wrong, what’s the deal?”, and then I realized that this is another hyperoptimization hack probably unique to Go: Go has no builtin max() function, so I had coded one, adding another function call to each iteration.

Since the implementation is so minimal as it is, that function call suddenly becomes very significant. Just swapping it over to an if-else immediately put me at 100%.

Which goes to show you that the runtime as a percentage of the “best” runtime is, at best, kind of bullshit. However, I learned another trick to game leetcode, so I suppose that’s something.