iT邦幫忙

1

動態規劃經典題: 最大子陣列之和

最大子陣列之和問題

參考題目: LeetCode 53. Maximum Subarray
一個陣列可能有正有負,求連續的子陣列的最大和(至少含一個元素)

範例測資
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

大問題與小問題之間的關聯性

我們需要找大問題與小問題之間的關聯性,
即如果我們知道前(i-1)個元素的陣列的最大子陣列之和,
有沒有辦法推出前i個元素的陣列的最大子陣列之和?

想法是這樣,從(i-1)個元素到多了第i個元素,要嘛

  • 前i個元素的最大子陣列包含第i個元素
  • 前i個元素的最大子陣列不包含第i個元素

這兩種可能中,取最大值就是答案了,
如果是第二種可能的話,
那答案很單純,
前i個元素的最大子陣列就是前(i-1)個元素的最大子陣列

如果是第一種可能,
那麼可能是最大子陣列串接到前(i-1)個元素包含第(i-1)個元素最大子陣列,
或者這個子陣列就單獨一個元素,只有第i個元素

程式碼實作

我們定義兩個變數resultcur
cur就是目前有包含最後一個元素的最大子陣列之和,
result就是目前的最大子陣列之和
一開始陣列只有一個元素的狀況之下,
最大子陣列只有唯一的可能,
初始值resultcur一定是nums[0]
再來逐次新增一個元素,更新resultcur的值,

要計算前i個元素的最大子陣列包含第i個元素的情況,
可能是最大子陣列串接到前(i-1)個元素包含第(i-1)個元素最大子陣列,
或者這個子陣列就單獨一個元素,只有第i個元素,
所以cur更新為cur + nums[i](串接前面的最大子陣列)與nums[i](只有第i個元素)的最大值

前i個元素的最大子陣列則是

  • 前i個元素的最大子陣列包含第i個元素
  • 前i個元素的最大子陣列不包含第i個元素
    這兩種情形的最大值,
    所以result會更新為result(不包含第i個元素,與前一個答案同)與cur(包含第i個元素)的最大值

程式如下:
<c++程式>

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0], cur = nums[0];
        for(int i=1; i<nums.size();i++){
            cur = max(cur + nums[i], nums[i]);
            result = max(result, cur);
        }
        return result;
    }
};

由於程式蠻簡單的,順便把python程式也打一打
<python程式>

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = cur = nums[0];
        for i in range(1, len(nums)):
            cur = max(cur + nums[i], nums[i])
            result = max(result, cur)
        return result

1 則留言

我要留言

立即登入留言