Skip to content

53. Maximum Subarray 最大子序和

难度: Medium

刷题内容

原题连接

  • https://leetcode.com/problems/maximum-subarray
  • https://leetcode-cn.com/problems/maximum-subarray

内容描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解题方案

思路 1

O(N^2)

从i开始,计算i到n,存比较大的sum,会超时

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        m = float('-inf')
        for i in range(n):
            s = 0
            for j in range(i,n):
                s = s + nums[j]
                m = max(m,s)
        return m 

思路 2

  • 动态规划(只关注:当然值 和 当前值+过去的状态,是变好还是变坏,一定是回看容易理解)
  • ms(i) = max(ms[i-1]+ a[i],a[i])
  • 到i处的最大值两个可能,一个是加上a[i], 另一个从a[i]起头,重新开始。可以AC
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        maxSum = [nums[0] for i in range(n)]
        for i in range(1,n):
            maxSum[i] = max(maxSum[i-1] + nums[i], nums[i])
        return max(maxSum)

思路 3

Kadane’s Algorithm wikipedia可以查到,然后一般的是负的可以还回0,这里需要稍作修改,参考

http://algorithms.tutorialhorizon.com/kadanes-algorithm-maximum-subarray-problem/

start:
    max_so_far = a[0]
    max_ending_here = a[0]

loop i= 1 to n
  (i) max_end_here = Max(arrA[i], max_end_here+a[i]);
  (ii) max_so_far = Max(max_so_far,max_end_here);

return max_so_far

AC代码:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        maxSum , maxEnd = nums[0], nums[0]

        for i in range(1,n):
            maxEnd = max(nums[i],maxEnd + nums[i])
            maxSum = max(maxEnd,maxSum)
        return maxSum

思路 4

参见clrs 第71页,用divide and conquer,有伪码

最大的subarray sum有三个可能,左半段或者右半段,或者跨越左右半段,

速度比较慢,AC代码,复杂度O(NlogN)

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def find_max_crossing_subarray(nums, low, mid, high):
            left_sum = float('-inf')
            sum = 0
            for i in xrange(mid,low-1,-1):
                sum = sum + nums[i]
                if sum > left_sum:
                    left_sum = sum

            right_sum = float('-inf')
            sum = 0
            for j in range(mid+1,high+1):
                sum = sum + nums[j]
                if sum > right_sum:
                    right_sum = sum

            return left_sum + right_sum

        def find_max_subarray(nums,low,high):
            if low == high: 
                return nums[low]
            else:
                mid = (low + high) / 2
                left_sum = find_max_subarray(nums, low, mid)
                right_sum = find_max_subarray(nums,mid+1,high)
                cross_sum = find_max_crossing_subarray(nums,low,mid,high)
                # print left_sum, right_sum, cross_sum
                # print mid, low, high
                return max(left_sum, right_sum, cross_sum)

        return find_max_subarray(nums, 0, len(nums)-1)


回到顶部