LeetCode小白菜笔记[13]：Maximum Subarray

53. Maximum Subarray [easy]

题目如下：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

这个题目是一个灰常经典的算法问题，就是最大子序列和问题，经常被包装成很多实际问题，比如股票价格变动已知的情况下何时买入何时出手能获得最大收益。有很多解法，分别具有不同的复杂度，从O(n^3)，O(n^2)到O(nlogn)以及O(n)都有，而且动态规划，分治算法都有应用。回去后在算法一栏中单独整理这个典型问题。现在只考虑用一种O(n)的算法来实现。

code如下：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        thismax = 0
        globalmax = nums[0]
        for i in range(len(nums)):
            if thismax > 0:
                thismax += nums[i]
            else:
                thismax = nums[i]
            if thismax > globalmax:
                globalmax = thismax
        return globalmax

基本思路如下：考虑一个数列，如果要找到最长子序列，可以遍历所有的子序列，然后每个子序列求和，比较大小，这样的话就是立方时间O(n^3)。这显然是不能接受的，于是考虑这个问题的最终结果具有哪些特性，从而可以略过一些循环。首先考虑到的是，对于最大和子序列来说，它的前缀，即第一个元素肯定不会是负数，因为如果前缀是负数，那么去掉前缀的一定比现有的大。所以可以在所有的遍历中，略过那些负数开始的序列。以这种思路继续延伸，我们发现：任何负的子序列也不是最优子序列的前缀，因为去掉它们会更优。所以我们维护一个thismax，也维护一个globalmax，globalmax就是最优解，而thismax指的是以某个位置的数字为后缀的子序列的最大值，循环到第i个数的时候，如果前面的子序列是正的，那么以第i个数为结尾的最大子序列，也就是此时的thismax，要保留前面的并且更新thismax = thismax + nums[i]。如果前面是负的，那么thismax就更新成nums[i]，然后每次都和globalmax比较，大于的话就更相信globalmax。最后返回globalmax就是最终结果，时间复杂度为线性O(n)。而且是常数空间，一颗赛艇~

2018年2月9日16:45:50

腊月二十四小年快乐~（虽然我们过二十三）