[Leetcode][python]Maximum Subarray/最大子序和

ゝ一世哀愁。 2022-06-07 02:28 136阅读 0赞

## 题目大意 ##

由 N 个整数元素组成的一维数组 (A\[0\], A\[1\],…,A\[n-1\], A\[n\])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？

子数组必须是连续的。  
不需要返回子数组的具体位置。  
数组中包含：正整数，零，负整数。

## 解题思路 ##

### Kadane Algorithm ###

官方标签为动态规划，这种算不算正经动态规划待定。  
可以理解为：

dp[i] = dp[i-1] + s[i] (dp[i-1] >= 0)
    dp[i] = s[i] (dp[i-1] < 0)

一旦前面总和<0,说明前面的加进去也是没用的，所以全部抛弃

list    -2 1 -3 4 -1 2 1 -5 4
    current -2 1  0 4  3 5 6 1  5
    m       -2 1  1 4  4 5 6 6  6

#### 动态规划 ####

class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            dp = [nums[0] for i in range(len(nums))]
            max_result = nums[0]  # 最开始的是nums[0]，后面如果是负数肯定更小，如果是整数肯定变大
            for i in range(1, len(nums)):
                if dp[i-1] < 0:
                    dp[i] = nums[i]
                else:
                    dp[i] = dp[i-1] + nums[i]
                if max_result < dp[i]:
                    max_result = dp[i]
            return max_result

#### 直接方法 ####

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

### 分治法 ###

对于任何一个array来说，有三种可能：  
　　　　　　1。它的maximum subarray 落在它的左边；  
　　　　　　2。maximum subarray 落在它的右边；  
　　　　　　3。maximum subarray 落在它的中间。

对于第一，二种情况，利用二分法就很容易得到，base case 是如果只有一个数字了，那么就返回。

对于第三种情况，如果落在中间，那么我们要从左右两边返回的两个 mss 中，挑出一个大的，再从 （左右中大的值） 和 （左+右）中挑出一个大的

[https://blog.csdn.net/u014235934/article/details/51996493][https_blog.csdn.net_u014235934_article_details_51996493]

而且对于左半部分或者右半部分，上述结论也成立，利用这特性，可以写出相应的递归，递归结束的条件是当只有一个元素时，判断这个元素是否大于零，大于零便返回这个数，否则返回零。  
然后求出左边最大值，右边最大值和横跨两边的最大值，返回这三个值中的最大值

class Solution(object):
        def maxSubArrayHelper(self,nums, l, r):
            if l > r:
                return -2147483647
            m = (l+r) / 2
    
            leftMax = sumNum = 0
            for i in range(m - 1, l - 1, -1):  # 从中间向左遍历
                sumNum += nums[i]
                leftMax = max(leftMax, sumNum)
    
            rightMax = sumNum = 0
            for i in range(m + 1, r + 1):  # 从中间向右遍历
                sumNum += nums[i]
                rightMax = max(rightMax, sumNum)
    
            leftAns = self.maxSubArrayHelper(nums, l, m - 1)
            rightAns = self.maxSubArrayHelper(nums, m + 1, r)
    
            return max(leftMax + nums[m] + rightMax, max(leftAns, rightAns)) # 返回三个中的最大值
    
        def maxSubArray(self, nums):
            return self.maxSubArrayHelper(nums, 0, len(nums) - 1)

## 总结 ##

该题分治法效率较低

[https_blog.csdn.net_u014235934_article_details_51996493]: https://blog.csdn.net/u014235934/article/details/51996493