letcode[053] 最大子序和

题目053

题目地址：最大子序和

思路1：自拟思路——暴力穷举法

列出所有可能的子串组合，对子串进行求和，返回求和的最大值
总结： 暴力解法，然而超出了时间限制。
用时： 超出时间限制 ms

nums=[-2,1,-3,4,-1,2,1,-5,4]
def maxSubArray(nums):
    #生成所有组合
    length=len(nums)
    sub_nums=[]
    #列出所有子串组合,each_len是每个子串的长度
    for each_len in range(length):
        j=each_len+1
        while j<=length:
            each_sub=nums[each_len:j]
            sub_nums.append(each_sub)
            j+=1
    #对每个子串求和
    sum_nums=[sum(each_list) for each_list in sub_nums]
    return max(sum_nums)

思路2：网友思路——动态规划？

传说中的动态规划思路。（看完思路3再看这个可能更易于理解）
1、先不考虑前面的计算结果是否有最优解问题。对于nums中的任意一个值i，和之前一个计算结果s之间，要选最优解存在两种情况：即s+i和i，选最大值即可max(s+i,i)，这就是局部最优解cursum。这里可以理解为，如果前面的数据计算出来的s是负数，则直接舍弃，从i开始再重新计算最优解。
2、还有一种情况无法避免，就是在计算出s前，全局最优解已经出现。所以，我们能要从第一个数开始，建立一个全局最优解变量maxsum，对于任意一个局部最优解，全局最优解即是已计算数据的全局最优解和当前局部最优解之间的最大值：maxsum = max(maxsum, cursum)
总结： 不愧是专家！
用时：72 ms

nums=[-2,1,-3,4,-1,2,1,-5,4]

def maxSubArray3(nums):
    cursum, maxsum = 0, nums[0]
    for i in nums:
        cursum = max(cursum+i, i)
        maxsum = max(maxsum, cursum)
    return maxsum

思路3：网友思路——扫描法（本质上和2是同一方法）

传说中的统计学家想到的方法。
引用一下解释：当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。
说人话是：

1. 我们对nums从左往右开始加和，会得到一个和原始nums相同长度的列表。
2. 在不限制条件的情况下，这样的结果，新的nums的每一位结果其实就是原nums到该位的累加值。
3. 现在限定了条件，需要求子序列的最大和。
4. 对于新的nums的第一位值，无法改变，即记为原始值。
   5. 对于第二位开始的任意一个，如果前面位数的结果小于0，那么加上本身只会使自己变得更小，所以该位就取这个值本身，否则就取前一位结果和自身的和。
5. 按上述思路计算出的结果如下：

old_nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]
new_nums=[-2, 1, -2, 4, 3, 5, 6, 1, 5]

7. 似乎有点儿明白了，生成的新列表第i位的值，即表示在该位置的局部最优解，那么对局部最优解求max，即是全局最优解。
8. 反过来看第2种思路，无非就是把此思路的集中求全局最优解的过程，纳入到了每一步中。
   总结： 统计学家的思路果然不一般。
   用时： 72 ms

def maxSubArray4(nums):
    for i in range(1, len(nums)):
        nums[i]= max(nums[i-1]+nums[i], nums[i])
    return max(nums)