Day 26：53. Maximum Subarray (2)

今日题目

题目连结：53. Maximum Subarray
题目主题：Array, Divide and Conquer, Dynamic Programming

这次的题目跟昨天一样，但是使用的解法跟主题是完全不同的，昨天使用的是 Divide and Conquer，今天会使用 Dynamic Programming，体验这个题目不同解法的感觉。

简单说说 Dynamic Programming

Dynamic Programming 动态规划，核心观念是用空间来优化效能。使用时也会将问题分解成小问题，找到一个规律出来，最後将小问题的答案都储存下来，每次往下一个问题找答案时可以使用前面存下来的答案来快速解决问题。

以费氏数列为例子，我们能找到的规律是一个数字一定会是前面两个数字的加总，因此我们在计算过程将每次的结果都记录下来，当算下一个数字时，只要拿前面两个数字加总就可以得到答案了，运作过程如下：

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个 nums 数字阵列，目的是要找出 nums 中每个连续的子集合总和後最大的值，最终回传这个最大的总和值。

约束：

• 1 <= nums.length <= 10的5次方
• -10的4次方 <= nums[i] <= 10的4次方

范例1

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解说: 
列出全部的连续子集合可能会有点多，这边只举几个例子:
[-2] = -2
[-2,1,-3,4] = 0
[4,-1,2,1] = 6
[2,1,-5,4] = 2
[-2,1,-3,4,-1,2,1,-5,4] = 1
上面是连续的子集合的例子，每个加总後可以看到[4,-1,2,1]总和的6最大，因此最後输出 6。

范例2

输入: nums = [1]
输出: 1
解说: 因为只有一个 1，因此最大也一定是 1。

范例3

输入: nums = [5,4,-1,7,8]
输出: 23
解说: 这个例子最大的就是[5,4,-1,7,8]加总後的23，因此最後输出23。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 宣告两个变数，预设约束最小值 -10的4次方 分别为：
   • currentMax: 记录目前使用连续子集的加总。
   • maxSum: 记录目前连续子集中加总的最大值。
2. 跑一个回圈，将每个值走过一次，每圈处理内容如下：
   • currentMax + 目前的值。
   • 确认要保留的值，更新目前使用的连续子集加总。
   • 确认要保留的值，更新目前连续子集中加总的最大值。

图解过程

范例：nums = [-3, 4, -1, 2, 1, -5, 4, -2]

上图是预设状态，我们会先宣告出 currentMax 及 maxSum，分别预设给他们约束的最小值 -10的4次方。

上图是回圈每一圈的处理过程，红色方框代表是更新过的最大总和，绿色方框是目前使用的子集，可以先看 step1 ~ step2 的变化，会发现当目前子集的总和没有大过现在的值，会保留现在的值，舍弃前面子集的总和，到了 step3 是直接从 4 开始往下去算总和，就不会把 -3 在算进来。

整体来看，可以看到在 step5 的时候，已经找到最大值 6 了，step6 ~ step8 的子集总和都没有再出现更大的值，因此会保留 6 到最後，这也是最终这个范例的答案。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 从最小值开始纪录
        currentMax = -10 ** 4
        maxSum = -10 ** 4
        # 每一圈都取一个值
        for num in nums:
            # 更新目前使用的连续子集加总
            currentMax = currentMax+num if currentMax+num > num else num
            # 更新目前连续子集中加总的最大值
            maxSum = currentMax if currentMax > maxSum else maxSum
        return maxSum

希望您今天能了解到...

1. Dynamic Programming 基本概念
2. 53. Maximum Subarray 使用Dynamic Programming的解法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：572. Subtree of Another Tree