在本篇文章中，我們將使用兩道 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（前綴和）是一種數據結構和算法技術，常用於高效地計算數組中任意區間的元素之和。它的核心思想是先構建一個前綴和數組，該數組中的每個元素都表示從數組開始到當前索引位置的所有元素之和。通過這樣的預處理，可以在常數時間內計算任何區間的和。

如下圖， 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 星期六