LeetCode Notes_#53 Maximum Subarray

LeetCode

Contents

题目
思路和解答
思路
解答
需要注意的点

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

思路和解答

思路

第一想法就是最简单的，直接暴力遍历整个数组，维护一个max变量，然后不断更新max的值，尝试一下

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

[2, 3, 4, 5]

#暴力算法，比较长的用例会超时....
maxSum=[-2,1,-3,4,-1,2,1,-5,4]
maxSum=nums[0]
tmpSum=0
for i in range(len(nums)):
    for j in nums[i:]:
        tmpSum=tmpSum+j
        maxSum=max(maxSum,tmpSum)
    # print 'tmp',tmpSum
    # print 'max',maxSum
    tmpSum=0
print (maxSum)

解答

#改进:如果遇到某个数，比前面的tmpSum+i还大(说明tmpSum<0)，那么可以直接从这里开始
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxSum=nums[0]
        tmpSum=0
        for i in nums:
            tmpSum=max(i,tmpSum+i)
            maxSum=max(maxSum,tmpSum)
        return maxSum

24ms,beat 99.98%

需要注意的点

暴力计算不可取，还是要找找规律...这道题就是需要判断符号，假如都是正数，那么肯定是元素越多，加起来越大；而为了简便，其实一旦发现tmpSum变为负，就说明需要重新开始了，那么就从两轮循环变成了一轮循环
遍历元素的时候，能不用下标就不用，容易越界