Как работает алгоритм Kadane (max subarray)?

LeetCode 53. Kadane's algorithm — O(n) для нахождения subarray с максимальной суммой. cur_sum — максимальная сумма subarray, заканчивающегося в текущей позиции.

def maxSubArray(nums):
    max_sum = cur_sum = nums[0]
    for x in nums[1:]:
        cur_sum = max(x, cur_sum + x)   # новый start или продолжение
        max_sum = max(max_sum, cur_sum)
    return max_sum

DP: dp[i] = max(nums[i], dp[i-1] + nums[i]), ответ = max(dp). Space optimization — нужно только dp[i-1], O(1) extra. Вариации: вернуть индексы (отслеживать start при reset), minimum subarray (заменить max на min), circular subarray (LeetCode 918: max(normal, total − min)), max product subarray (отслеживать max и min для отрицательных).