在本篇文章中，我們將使用兩道 LeetCode 原題來解釋 Maximum Subarray Sum 問題，並介紹用於解決這類問題的著名演算法 Kadane's Algorithm 。透過這些例題和演算法的解釋，希望能夠幫助讀者更好地理解這個問題，並學會使用 Kadane's Algorithm 來解決。

Leecode #53 Maximum Subarry

題目要你從陣列中找出最大 Subarray sum ，以下探討兩個做法。

方法 1 Kadane's algorithm

走訪整個陣列，每經過一個陣列元素，可以決定出"以該筆資料為 subarray 結尾"的 maximum subarray sum ，這樣的 maximum subarray 有以下兩種可能 :

1. 前一個陣列元素做為 subarray 結尾的 maximum subarray sum 再加上當前陣列元素
2. 當前陣列元素

有了以各個陣列元素為結尾的 mamimum subarray sum 後，從中挑出最大值，就是 input array 中的 maximum subarray sum 。

而這個方法背後就是動態規劃的概念，動態規劃一大特徵是最佳子結構，即透過每個子問題的解來推導出問題的最佳解。

動態規劃的第一步即定義出陣列元素:

dp[i] 定義為包含 data[i] 的最大 subarray sum 。

接著定義出遞迴關係式:

dp[i] = max (dp[i-1] + data[i] , data[i]);

方法 2 Prefix Sum

Prefix Sum 代表一個 array 隨著 index 前進累計下來的總和， prefix[i] = array[0] + ... array[i-1] 。如下圖:

而 prefix[i+1] - prefix[j] 代表從 Index j 到 index i 所形成的 subarray sum，這個 j 可能是 index 0 到 i-1 ，也意味著可以透過這個算法找出所有以 index i 為結尾元素的 subarray 。

從這個概念延伸，如果 prefix[j] 越小，也就代表找出以 index i 為結尾元素的 subarray sum 越大。

因此 maximum subarray sum 等於 prefix[i+1] - min (prefix[1], prefix[2], … prefix[i]) 。

Leetcode #2321 Maximum Score Of Spliced Array

如果想要讓 nums1 array 總和最大化，盡可能要讓較大的 nums2 array 元素換到 nums1，意味著要找出由 index i 到 j 所形成的 subarry 並具備最大的陣列差 nums2[i..j] - nums1[i..j] 。換句話說，我們定義一個由陣列元素差所形成的 subarray ，從中找出最大的 subarray sum ，就是需要被交換的 subarray 。
從陣列差形成的 subarray 找出 maximum subarray sum 就可以透過 Kadane's algorithm 。

class Solution {
public:
    int kadane_helper (vector<int>& nums1, vector<int>& nums2) {
        int size = nums1.size();
        vector<int> diff(size);

        for (int i=0; i<size; i++) {
            diff[i] = nums1[i] - nums2[i];
        }
        int result = INT_MIN;
        int sub_sum = 0;
        for (int i=0; i<size; i++) {
            sub_sum = std::max (sub_sum+diff[i], diff[i]);
            result = std::max (result, sub_sum);
        }
        return result;
    }

    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {

        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);

        int max_diff1 = kadane_helper (nums1, nums2);
        int max_diff2 = kadane_helper (nums2, nums1);

        return std::max (sum1+max_diff2, sum2+max_diff1);
    }
};

Reference

1. 最大子數列問題-Wikipedia
2. 动态规划设计：最大子数组

Updated on 2023-01-07 13:48:24 星期六