Maximum Subarray

曾经终败给现在 2021-12-17 10:39 141阅读 0赞

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`.

这个一道非常经典的题目，剑指offer上也有。

用DP做思路是最优的，但是DP的做法本身有很多种解释。一种是用f\[i\]表示以第i 个元素结尾的子数组的最大和。最后的最大和为max(f\[i\])。

另外一种解释是使用local, global的解法，即我们的f\[i\]是local, maxsum为global.

其实是用后一种解释更加合理，两种解释的代码也很相同，代码如下：

class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            res = [0] * (len(nums)+1)
            maxsum = -sys.maxint-1
            for i in xrange(1, len(nums)+1):
                if res[i-1] <= 0:
                    res[i] = nums[i-1]
                else:
                    res[i] = res[i-1] + nums[i-1]
                maxsum = max(maxsum, res[i])
            return maxsum

另外一种解释是：

class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            Local = nums[0]
            Global= nums[0] 
            for i in xrange(1, len(nums)):
                Local = max(Local + nums[i], nums[i])
                Global = max(Local, Global)
            return Global

转载于:https://www.cnblogs.com/sherylwang/p/5628176.html