[关闭]
@liweiwei1419 2019-02-10T15:02:42.000000Z 字数 2608 阅读 1264

LeetCode 第 53 题:连续子数组的最大和

动态规划 分治法



传送门:53. 最大子序和

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

示例:

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

进阶:

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

分析:
image-20190110155725094

总结:分类讨论的标准是:若之前的和小于 0,则将最大和置为当前值,否则计算最大和。

思路1:动态规划

下面展示了标准的动态规划的写法。

Java 代码:

  1. public class Solution {
  2. public int FindGreatestSumOfSubArray(int[] array) {
  3. int n = array.length;
  4. if (n == 0) {
  5. return 0;
  6. }
  7. int[] dp = new int[n];
  8. dp[0] = array[0];
  9. int res = array[0];
  10. for (int i = 1; i < n; i++) {
  11. dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
  12. res = Integer.max(res, dp[i]);
  13. }
  14. return res;
  15. }
  16. public static void main(String[] args) {
  17. int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
  18. Solution solution = new Solution();
  19. int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
  20. System.out.println(findGreatestSumOfSubArray);
  21. }
  22. }

这道题主要就在状态的定义上要思考一下,这里题目中的关键字是“连续”,所以如果我们定义的状态就是题目要求的结果:dp[i] 表示 nums 在区间 [0,i] 中连续子数组的最大和,那么在思考状态转移方程的时候,dp[i] 之前的,例如 dp[i-1] 就有可能是是更前面的连续子数组的最大和,不利于我们分类讨论。

因此,我们可以定义状态:dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。

这样定义状态,分类讨论就变得容易多了,因为 dp[i-1] 表示一定以 nums[i-1] 结尾,那么 dp[i] 就可以有两种情况:

1、把 nums[i] 直接接在 dp[i-1] 表示的那个数组的后面;

例如,dp[i-1] = 3,nums[i] = 5,当然接在后面,越接越大。

2、单独的一个 nums[i] 。

这种情况也比较好想到,比如:dp[i-1] = -3,nums[i] = 5,加上前面的数反而我越来越小了,干脆我另起炉灶吧。

以上两种情况的最大值就是 dp[i] 的值。

最后不要忘记了,最终的结果应该是把所有的 dp[0],dp[1],……,dp[n-1] 都看一遍,求最大值。

重点:动态规划问题。状态是:以当前数字为结尾的连续子数组的最大和。

Python 代码:

  1. class Solution(object):
  2. def maxSubArray(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: int
  6. """
  7. l = len(nums)
  8. if l == 0:
  9. return 0
  10. if l == 1:
  11. return nums[0]
  12. dp = [0 for _ in range(l)]
  13. dp[0] = nums[0]
  14. for i in range(1, l):
  15. dp[i] = max(dp[i - 1] + nums[i], nums[i])
  16. # 最后不要忘记拉通求一遍最大值,或者在上面遍历的时候,就保存最大值
  17. return max(dp)

或者你可以在遍历的时候,就把最大值求出来。

  1. class Solution(object):
  2. def maxSubArray(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: int
  6. """
  7. l = len(nums)
  8. if l == 0:
  9. return 0
  10. # 以索引 i 结尾的最大子数组的和
  11. end_i_max = nums[0]
  12. # 最后返回的数
  13. res = nums[0]
  14. for i in range(1, l):
  15. # 例:[-3,1]
  16. end_i_max = max(nums[i], end_i_max + nums[i])
  17. res = max(res, end_i_max)
  18. return res

思路2:分治法

参考资料:连续子数组最大和

Python 写法:

  1. class Solution(object):
  2. def maxSubArray(self, nums):
  3. """
  4. :type nums: List[int]
  5. :rtype: int
  6. """
  7. n = len(nums)
  8. if n == 0:
  9. return 0
  10. return self.__max_sub_array(nums, 0, n - 1)
  11. def __max_sub_array(self, nums, left, right):
  12. if left == right:
  13. return nums[left]
  14. mid = left + (right - left) // 2
  15. return max(self.__max_sub_array(nums, left, mid),
  16. self.__max_sub_array(nums, mid + 1, right),
  17. self.__max_cross_array(nums, left, mid, right))
  18. def __max_cross_array(self, nums, left, mid, right):
  19. """
  20. 一定包含 nums[mid] 元素的最大连续子数组的和
  21. 思路是看看左边扩散到底,得到一个最大数
  22. 右边扩散到底得到一个最大数
  23. :param nums:
  24. :param mid:
  25. :param right:
  26. :return:
  27. """
  28. ls = 0
  29. j = mid - 1
  30. s1 = 0
  31. while j >= left:
  32. s1 += nums[j]
  33. ls = max(ls, s1)
  34. j -= 1
  35. rs = 0
  36. j = mid + 1
  37. s2 = 0
  38. while j <= right:
  39. s2 += nums[j]
  40. rs = max(rs, s2)
  41. j += 1
  42. return ls + nums[mid] + rs
  43. if __name__ == '__main__':
  44. s = Solution()
  45. nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  46. result = s.maxSubArray(nums)
  47. print(result)

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注