Maximum Subarray Problem

Leetcode #53 Maximum Subarray Problem

最大子数组

最大子数组问题 Maximum Subarray Problem: 描述的是在给定的一个数字类型非空数组里面，求其最大连续子数组的和。
例如[1,-2,-3,-4,5]的最大子数组和为5，而对于[1,-2,-3,-4,5,1]为5+1 = 6。更为复杂且经典的例子为[-2,1,-3,4,-1,2,1,-5,4]该最大子数组的和为4-1+2+1=6

做这种题目，暴力算法固然简单，但程序的时间复杂度会极高。例如这里暴力解，用for loop套for loop就可以解决。但是会有time exceed 这种问题。
像我这种废物，只能去搜一搜有什么好的算法能更快去解决(其实我有想到部分kadane的逻辑，但是组织不起来)

Kadane's Algorithm

Kadane's Algorithm 是用于解最大子数组一个算法。其时间复杂度为O(n)。
那么Kadane's Algorithm是怎么运作的呢？让我们从经典的例子开始讲起，

1. 给定一个值，当该值前面的最大子数组与该值的和 小于 该值时候，不如从该值开始。例如1-3+4<4,我们就应该舍弃前面的数，直接从4开始加
2. 为了保证和最大，每次连续加上一个新值时与未加的状态做对比，保留最大的值。例如4-1<4,我们保留4最为最终答案，如果-1后面没有值/全是负值，那么4为最终答案无误。例如4-1+2>4我们则保留4-1+2，注意此处的4是从之前与4-1<4得到的局部最大和。
3. 至此在遍历一遍列表即可得到 局部最大和。例如 4-1+2+1>4-1+2+1-5 && 4-1+2+1> 4-1+2+1-5+1得到4-1+2+1为最后结果

用python写出

def max_sub(lst):
    # lst非空
    local_max = sub_max = lst[0] # 从第一位开始
    for num in lst[1:]:
        sub_max = max(num, sub_max + num) # 对比之前的和+该值与该值本身大小 第一步
        local_max = max(sub_max, local_max) # 保留局部最大值 第二步
    return local_max

D&C Induction(recursion)

Divide & Conquer 也可以做，到时候会写这个更常用的算法。