Leetcode 1749. 任意子陣列的最大絕對和

題目描述

#

給定一個整數陣列 nums，定義子陣列 [nums_l , nums_{l+1}, ... , nums_r] 的絕對和為 abs(nums_l + nums_{l+1} + ... + nums_r)。

請回傳 nums 中任意（可為空）子陣列的最大絕對和。

注意：abs(x) 的定義如下：

• 若 x 為負數，則 abs(x) = -x
• 若 x 為非負數，則 abs(x) = x

解題思路 - 前綴和

#

• 我們知道子陣列的總和可以表示為兩個前綴和之差。
• 因此，最大絕對和等於「最大前綴和」減去「最小前綴和」。

Code

#

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int prefixSum = 0;
        int maxSum = 0;
        int minSum = 0;
        for(int num : nums){
            prefixSum += num;
            maxSum = max(prefixSum, maxSum);
            minSum = min(prefixSum, minSum);
        }
        return maxSum - minSum;
    }
};

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

感謝閱讀！歡迎留言分享你的想法與回饋！