53. Maximum Subarray 真的不容易 Kadane's algorithm

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:
Input: nums = [1]
Output: 1

强行解法 O(n^2)

代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max=nums[0]
        for i,num in enumerate (nums):
            sum = num
            if(sum>max):
                    max=sum
            for j in range(i+1,len(nums)):
                 sum=sum+nums[j]
                 if(sum>max):
                    max=sum
        return max

我们将每种subarray的可能性都算进去，并一直更新出现过的最大值。很明显这种解法实在是太慢了！！！！leetcode根本不让你通过的，比如100个数据100^100次循环 天知道要跑多久。

神奇的Kadane’s algorithm

代码

'''
The Idea:
1. We have to find the sum of "contiguous" subarray, therefore we must not change the order of array elements.
2. Let `current_sum` denotes the sum of a subarray, and `max_sum` denotes the maximum value of `current_sum`.
3. LOOP STARTS: For each element of the array, update the `current_sum` with the MAXIMUM of either:
 - The element added to the `current_sum` (denotes the addition of the element to the current subarray)
 - The element itself  (denotes the starting of a new subarray)
 - Update (overwrite) `max_sum`, if it is lower than the updated `current_sum`
4. Return `max_sum`
'''

'''
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_current = max_global = nums[0]
        for num in nums[1:]:
            max_current = max(num,max_current+num)
            if(max_current>max_global):
                max_global = max_current
        return max_global        
'''    
def max_sum_subarray(arr):

    current_sum = arr[0] # `current_sum` denotes the sum of a subarray
    max_sum = arr[0]     # `max_sum` denotes the maximum value of `current_sum` ever

    # Loop from VALUE at index position 1 till the end of the array
    for element in arr[1:]:

        '''
        # Compare (current_sum + element) vs (element)
        # If (current_sum + element) is higher, it denotes the addition of the element to the current subarray
        # If (element) alone is higher, it denotes the starting of a new subarray
        '''
        current_sum = max(current_sum + element, element)

        # Update (overwrite) `max_sum`, if it is lower than the updated `current_sum`
        max_sum = max(current_sum, max_sum)   

    return max_sum

分析

kadane’s algorithm 示例和证明（从5:31左右开始）

假设之前造成最大值的subarray是M，当for loop 开始循环后，每遇到一个值，我们判断是否要取X,即
max_current = max(num,max_current+num)
即当前在index nth时（截止到并包括X），当前造成最大值的subarray=max([X],[M,X])，也就是我们到底要不要之前的M。通过观察我们可以发现以下规律

到这一步，我们确定了max_current 的值。此时我们还需要进一步将max_current与记录中的max_global (nums[1…n-1]中history_subarray历史最大值)进行比较,决定是否更新历史最大值。

算法到这里就结束了，但是还有一个需要解释的地方，也就是curr_array的巧妙之处。我们首先要明确curr_array一定要包含当前的X，这样的目的在下一个循环中就会显现出来。第n次中我们找到的curr_array会变成第n+1次中的M，至此，第n+1位的循环中判断条件与上一次完全一致。prove by induction, curr_array的结果从1至n次循环都会给出正确结果。

评论区中的极简神奇解法

for i in range(1, len(nums)):
    if nums[i-1] > 0:
        nums[i] += nums[i-1]
return max(nums)

作者的思路原话

分析

其实思路和kadane’s algorithm是一样的， M不为负数，curr_subarray = [M,X], 把max_current更新在num[i]上。否则直接抛掉M,在下一次循环中直接取curr_subarray = [X]。最后再返回max(nums)，当然，返回的项肯定是被max_current更新过的元素。