E-53. Maximum Subarray

如果这题没有头绪, 或者看不懂我下面的东西的话, 可以看看这个哥们的视频, 另外他频道里的东西都很有意思, 刚开始刷题的话, 无聊的时候可以去看几个视频. 是现在在马里兰帕克读书的很聪明的一个小兄弟.

7:49 开始讲DP的解法, 前面在讲暴力解, 不感兴趣可以略过

# 1 dp
'''
先尝试把问题转换成一个可解的版本: 
    给一串数nums = [1,2,3,4,...], 找到一个subarray, 使得subarray中数字的sum是所有subarray
    中最大的那个subarray, 返回sum即可(不需要保存subarray, 保存也差别不大应该..).
    因为subarray有起始点和终止点, 我们可以用array[s,e](inclusive)来表示某个唯一的subarray.
s和e分别是数字在nums里的下标. 因此我们要求, 使得array[s,e]中数字的sum最大的那个array[s,e]的sum
    => 而这个maxsubarray[s,e]实际上是由s和e来定义的. 所以问题变成了找到那个s和e.
    => 但是一顿绞尽脑汁都不知道如何快速地找s和e(非暴力), 看来我们需要站在更高的角度看问题, 我们是不是不需
    要找到那个s和e?而可以直接得出那个sum? how?
=============================================================
说实话我也不知道如果我没看答案该怎么思考这个题目, 但是如果我们看了答案, 再回来反思, 可以进行如下思考:
    
    既然我们要找有最大sum的那个subarray, 而且每一个subarray都有一个右边界, 如果我们能找到这个
    nums中所有的, 以某一个index为右边界的所有subarray中sum最大的那个subarray的sum, 我们记作sum_i
    , 然后从中选最大的那个sum, 即是我们要找的结果.
    
    所以我们有了以下思路:

    设f[i]是 -> *如果nums[i]一定在该maxSubArray里的情况下*, 下标0到i的maxSubArray的值(所谓下标0到
    i的maxSubArray的意思是, 假设我们已经遍历过一次nums中下标为0到i的数, 我们得到了一个maxSubArray
    , 这个maxSubArray的sum()是f[i])
    
    
                ---f[i] = max(nums[i] + f[i-1], nums[i])   i > 0
    我们不难发现-- 
                ---f[0] = nums[0]                          i == 0
                    
    (或者对于i>0, 可以写作另一种形式f[i] = nums[i] + f[i-1] 
                                        if f[i-1] > 0
                                        else nums[i])
                
    因此对于nums=[-2,1,-3,4,-1,2,1,-5,4]
        从左往右遍历nums: 
        1. 遍历到nums[0]的时候, 显然f[0] = maxSubArray = nums[0] = -2
        2. 遍历到nums[1]的时候, f[1] = maxSubArray如何计算呢?
           对于此时的f[1]来说, 有以下2种选择, 根据开头的定义, f[1]就意味着第1号位置的数一定在maxSubArray
           中, 所以我们要看f[0]到底要不要接着参与到f[1]中, 即:
               1. 不舍弃f[0], 并且加上当前的nums[1]组成新的f[1] = f[0] + nums[1] = -1
               2. 舍弃f[0], 从当前的nums[1]重新开始纳入maxSubArray, f[1] = nums[1] = 1
               (再次强调, 根据定义, 因为f[1]一定会取nums[1], 所以并不存在nums[1]被舍弃的情况.)
               
           而, 是否舍弃f[0], 显然要看f[0]对f[1]的影响是正面的还是负面的. 
           对于这道题显然要选择让f[1]最大化的情况. 
           而在这道题目里, 让f[1]最大化的情况就是f[0]>0.
           即我们选择 which is the max(f[0] + nums[1], nums[1])
           (
           所以下面的code循环里的那一行能改成这样:
           max_sum_lst.append(max([nums[i] + max_sum_lst[i-1],nums[i]]))
           )
        3. ...递推即可
    所以我们能得到上面的公式
    最终我们从f[0]到f[n]中选出最大的那个f[i]即可.
'''
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return None
        if len(nums)==1:
            return nums[0]
        max_sum_lst=[nums[0]]
        for i in range(1,len(nums)):
            max_sum_lst.append(nums[i] + max_sum_lst[i-1] if max_sum_lst[i-1] > 0 else nums[i])
        return(max(max_sum_lst))

Maximum subarray problemWikipedia