iT邦幫忙

1

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

循環陣列的最大子陣列之和問題

參考題目: LeetCode 918. Maximum Sum Circular Subarray

一個陣列可能有正有負,求連續的子陣列的最大和(至少含一個元素)

範例測資
Input: [5,-3,-3, 5]
Output: 10
Explanation: 子陣列[5,5] 有最大和10

在解這一題之前,首先我們複習一下動態規劃經典題: 最大子陣列之和這題
這兩題其實非常的像,
差別在循環陣列的最右端是繞回來連接左邊的,
因此最大總和的子陣列有可能是:

  1. 正常的子陣列
  2. 從右邊繞回左邊的子陣列

想法其實很簡單,兩種答案都算一下,取較大的答案就行了
第一種算最大子陣列之和的方法已經在上次求解過了

要求從右邊繞回左邊的子陣列的最大值其實有個巧思,
那就是計算去除陣列首尾的「最小子陣列之和」(類似最大子陣列之和的算法,請舉一反三),
用整個陣列的數字總和去扣掉「最小子陣列之和」,
即得到從右邊繞回左邊的子陣列的最大值

程式碼如下:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        
        //第一部分: 求解正常的最大子陣列之和問題
        int result_max = nums[0], cur_max = nums[0];
        for(int i=1; i<nums.size();i++){
            cur_max = max(cur_max + nums[i], nums[i]);
            result_max = max(result_max, cur_max);
        }
        
        //在陣列大小大於2時,才需考慮從右邊繞到左邊的子陣列
        if(nums.size()<2){
            return result_max;
        }
        
        //求陣列的數字總和
        int sum = 0;
        for(int i=0; i<nums.size();i++){
            sum += nums[i];
        }
        
        //第三部分: 求解最小子陣列之和問題 (只看陣列[1, size-1)中間位置的元素)
        int result_min = 0, cur_min = 0;
        for(int i=1; i<nums.size()-1;i++){
            cur_min = min(cur_min + nums[i], nums[i]);
            result_min = min(result_min, cur_min);
        }
        return max(result_max, sum - result_min);       
    }
};

哦,對了,在小馬的解答中,三個for迴圈是可以合併成一個的,
只是小馬覺得這個分開寫看的比較清楚,
若希望程式碼短一些,可以參考LeetCode All in One- 918上的解法


尚未有邦友留言

立即登入留言