Day 25：53. Maximum Subarray (1)

今日题目

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

简单说说 Divide and Conquer

Divide and Conquer的主要概念就是Divide 分割、Conquer 克服这两个，意思是会把一个大问题一层一层的分割成小范围的问题，一直到不能再分割为止，之後再一层一层的往上克服拿到整个大问题的答案。

下面是一个常见的例子，有一种排序方法叫Merge Sort，是用Divide and Conquer概念来实作的，

Divide:

一层一层向下去切割成小范围，直到不能再切割。

Conquer:

一层一层往上去解决目前的问题，这边解决的问题就是排序，每往上一层就会排序好一个范围，走到最上层就会将整个阵列里面的数字从小到大排序好。

题目解说

建议可以看看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. 写一个递回方法，传入nums、开始位置、结束位置，每一次呼叫会处理以下：
   • 用开始位置及结束位置找中间位置。
   • 将目前范围 nums 以中间位置开始切成左边及右边两个子集合。
   • 取得左边连续子集总和後的最大值。
   • 取得右边连续子集总和後的最大值。
   • 取的中间连续子集总和後的最大值。
   • 最後向上回传左边、右边、中间之中最大的总和值。
2. 这个递回方法，会一直切到不能再切割为止，最终全部走完会回传所有连续子集总和後的最大值。

图解过程

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

上图中是使用Divide and Conquer的运作过程，红色的方框是每一次的切割点每往下一层会切成三个部份，leftMax、crossMax、rightMax，可以先特别看看crossMax的部份绿色方框代表现在crossMax这个范围总和最大的子集。

接着，每一层都会得到一个粗体的数字代表是目前这一层范围的子集合中最大的总和，将这个值在往上传，跑回到最上层就可以拿到整体范围的Max值，就是这个范例的答案了。

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

程序码撰写

class Solution:
    # 取得中间子集合最大值
    def getCrossMax(self, nums, startIndex, middleIndex, endIndex):
        crossLeft = 0
        crossRight = 0
        tmpValue = 0
        # 从中间向左走最大子集合
        for i in range(middleIndex-1, startIndex-1, -1):
            tmpValue += nums[i]
            crossLeft = max(tmpValue, crossLeft)        
        tmpValue = 0
        # 从中间向右走最大子集合
        for i in range(middleIndex+1, endIndex+1):
            tmpValue += nums[i]
            crossRight = max(tmpValue, crossRight)
        # 将左中右的值都相加後，为中间子集合最大值
        return crossLeft + nums[middleIndex] + crossRight
    
    # 取得最大值
    def getMax(self, nums, startIndex, endIndex):
        # 若开始位置超过结束位置，代表剩一个值，回传当下的值
        if startIndex >= endIndex:
            return nums[startIndex]
        # 找到中间位置
        middleIndex = int((startIndex + endIndex)/2)
        
        # 取得左边子集合最大值
        leftMax = self.getMax(nums, startIndex, middleIndex-1)
        # 取得右边子集合最大值
        rightMax = self.getMax(nums, middleIndex+1, endIndex)
        # 取得中间子集合最大值
        crossMax = self.getCrossMax(nums, startIndex, middleIndex, endIndex)
        # 找到目前范围的最大值
        return max(leftMax, rightMax, crossMax)
        
    def maxSubArray(self, nums: List[int]) -> int:
        return self.getMax(nums, 0, len(nums)-1)

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

1. Divide and Conquer 基本概念
2. 53. Maximum Subarray 使用Divide and Conquer的解法

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

Next：53. Maximum Subarray - Dynamic Programming