LeetCode: 1749. Maximum Absolute Sum of Any Subarray 解題紀錄

Last Updated on 2025-02-26 by Clay

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

---

解題思路

這題目要我們在一組數值陣列中，找到連續子陣列的加總絕對值最大值 —— 這意味著我們不只要考慮正數的加總、也要考慮負數的累加。

我的解法是分別儲存當前的最大值累積和最小值累積，並不斷在更新數值後比對整體的最大值與最小值；需要額外做的處理是當『最大值累積 < 0』以及『最小值累積 > 0』時直接將其設置為 0，這就像是不要拖著負資產繼續累積一樣。

最後，在比較最大值和最小值的絕對值何者為大，其就是答案。

這個解法只需要掃過原始陣列一次、並宣告 4 個 INT 參數即可。所以時間複雜度是 O(n)，空間複雜度是 O(1)。

C++ 範例程式碼

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        // Find the maximum and minimum
        int _max = 0;
        int _min = 0;
        int _currMax = 0;
        int _currMin = 0;

        for (int num: nums) {
            _currMax = max(_currMax + num, 0);
            _currMin = min(_currMin + num, 0);

            _max = max(_currMax, _max);
            _min = min(_currMin, _min);
        }

        return max(_max, std::abs(_min));
    }
};

Python 範例解法

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        # Init
        _max = 0
        _min = 0
        curr_max = 0
        curr_min = 0

        # Find the maximum and minimum
        for num in nums:
            curr_max = max(curr_max + num, 0)
            curr_min = min(curr_min + num, 0)
            _max = max(_max, curr_max)
            _min = min(_min, curr_min)

        return max(_max, abs(_min))
        

---

References

• 1749. Maximum Absolute Sum of Any Subarray

---

Read More

• LeetCode 解題紀錄目錄