[LeetCode][Python]53. Maximum Su

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.

思路：1. 取数组的第一个元素当做当前最大值curSum和最终最大值maxSum。然后从list第一个元素开始。如果num是正数，则将curSum+num赋给curSum。然后将curSum赋给maxSum。如果num是负数，则取num和curSum+num之间的大值(因为curSum+num的值有可能小于num的)，在将curSum和maxSum之间的大值赋给maxSum。

1. 依次从第一个元素遍历list，然后比较nums[i]和nums[i] + nums[i-1]的大小，到第i个值的时候，这时候nums[i]是当前最大，如果继续遍历下去，就是比较nums[i+1]+nums[i]和nums[i+1]的大小，如果nums[i+1]是正值，则毫无疑问nums[i+1]+nums[i]大，如果nums[i+1]小于0，则取nums[i+1]+nums[i]和nums[i+1]的大值，依次循环下去，nums里面就会保留每次循环的大值，最后在其中选取最大值。

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        curSum = maxSum = nums[0]
        for num in nums[1:]:
            curSum = max(num, curSum + num)
            print num, "curSum:", curSum
            maxSum = max(curSum, maxSum)
            print "maxSum:", maxSum

        return maxSum

    def maxSubArray2(self, nums):
        for i in xrange(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i-1])
            print i, " == ", nums
        return max(nums)



if __name__ == '__main__':
    sol = Solution()
    s = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    # print sol.maxSubArray(s)
    print sol.maxSubArray2(s)