算法@LeetCode:MaximumSubarray

Log

• 【170419】完成 01 版（Python）提交（正确提交）与笔记

题目

Maximum Subarray

【题目类型备注】

数组, 动态规划, 分治法

提交

01

【语言】

Python

【时间】

170419

【思路】

（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）

这种看似贪心、细想可用 O(n^2) 时间复杂度暴力搜索完、但实际上求有增有减的子序列和的问题是典型的动态规划（DP, Dynamic Programming）问题。显然理想情况下若 DP 算法设计正确，只要 O(n) 的时间复杂度即可求得解。

为了实现 DP，需要记录每一步的状态，以便 n 规模的问题可以化为 n-1 规模的问题，即

已知 n-1 规模的最大子序列和，如何变成 n 规模的最大子序列和问题？

那么无非 2 种情况：

1. subsum[n] = subsum[n-1] + nums[i]：显然，若 subsum[n-1] > 0，是这种情况，因为这样的和会让 subsum[n] 更大（比起不用 subsum[n-1] 来说）
2. subsum[n] = 0 + nums[i]：若 subsum[n-1] < 0，那么与其用 subsum[n-1]，不如直接用 nums[i]（由于 subsum[n-1] < 0，所以有 subsum[n-1] + nums[i] < 0 + nums[i]）

那么就很容易写出代码了。

【代码】

class Solution(object):
    def maxSubArray(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          resultNow = nums[0]
          submax = [nums[0]]

          for i in range(1, len(nums)):
            if submax[i-1] > 0:
              submax.append(submax[i-1] + nums[i])
            else:
              submax.append(0 + nums[i])
            resultNow = max(submax[i], resultNow)

          return resultNow

【结果】

运行时：69 ms

报告链接：https://leetcode.com/submissions/detail/100564851/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 30.23% of python submissions.

P.S. 其实我昨天最开始的思路已经非常接近这个答案了，但没有抓住最开始正确的直觉，而且对于「n 规模的问题与 n-1 规模的问题之间的关系」没足够明确，还多考虑了一种「subsum_max 不在 n-1 上，而是在 n-k 上，与 n 之间还隔着一些数，不确定要不要加上这些数」的情况……总之，对于动态规划问题，关键还是抓住 n 规模问题与 n-1 规模问题之间的联系，写出状态方程。

00

参考解法：

• Java
  • Java（this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)）

自己实现一遍最优解：

• Python
• 。。。