題目資訊

• 題目編號: 1749
• 題目連結: Maximum Absolute Sum of Any Subarray
• 主題: Array, Dynamic Programming

題目敘述

你有一個整數數組 nums。子數組 $[nums_l, nums_{l+1}, …, nums_{r-1}, nums_r]$ 的絕對和為 $abs(nums_l + nums_{l+1} + … + nums_{r-1} + nums_r)$。

返回 nums 的任何 (可能為空的) 子數組的最大絕對和。

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

• 如果 x 是一個負整數，則 abs(x) = -x。
• 如果 x 是一個非負整數，則 abs(x) = x。

範例 1:

輸入: nums = [1,-3,2,3,-4]
輸出: 5
解釋: 子數組 [2,3] 的絕對和 = abs(2+3) = abs(5) = 5。

範例 2:

輸入: nums = [2,-5,1,-4,3,-2]
輸出: 8
解釋: 子數組 [-5,1,-4] 的絕對和 = abs(-5+1-4) = abs(-8) = 8。

約束條件:

• $1 \leq nums.length \leq 10^5$
• $-10^4 \leq nums[i] \leq 10^4$

直覺

這個問題要求找到子陣列的最大絕對和，其可能完全正數、完全負數或為空（產生零）。這本質上是動態調整子陣列和的問題，同時檢查其絕對值。我們可以使用類似於Kadane演算法的技術計算最大子陣列和，動態計算最大和最小可能的和，並使用它們確定遍歷過程中出現的最大絕對和。

解法

此解法涉及維護兩個連續的和：一個用於正子陣列，另一個用於負子陣列。這些對應於子陣列和的潛在正負極限，隨著陣列的遍歷變化。

1. 初始化變數: 我們首先定義三個變數：

   • positiveSum：這追蹤在任何給定位置結束的子陣列的最大可能和，子陣列和為非負數。初始化為0。
   • negativeSum：這紀錄最大可能的負子陣列和。我們通過將元素視為子陣列的負貢獻來處理這個（即，減去而不是加上）。初始化為0。
   • maxAbsSum：這儲存遇到的 positiveSum 或 negativeSum 的最大絕對值，最初設定為0。

2. 遍歷陣列: 我們遍歷 nums 中的每個元素 element：

   • 更新正和：將當前元素加到 positiveSum。如果這導致負和，將 positiveSum 重設為0。這符合正子陣列和不能從負貢獻中獲益的事實。 $$ \text{positiveSum} = \max(0, \text{positiveSum} + \text{element}) $$
   • 更新負和：從 negativeSum 減去當前元素。這模擬將元素視為負運行和的正貢獻。如果 negativeSum 變得小於0，重設為0，重設未來潛在負最小值評估的上下文。 $$ \text{negativeSum} = \max(0, \text{negativeSum} - \text{element}) $$

3. 比較並儲存最大絕對和：對於每一步，將當前的 positiveSum 和 negativeSum 與 maxAbsSum 比較並保留最大的。 $$ \text{maxAbsSum} = \max(\text{maxAbsSum}, \max(\text{positiveSum}, \text{negativeSum})) $$

4. 返回結果: 在處理完 nums 中的所有元素後，maxAbsSum 包含任何子陣列的最大絕對和，作為結果返回。

程式碼

C++

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int positiveSum = 0;  // 追蹤最大正子陣列和
        int negativeSum = 0;  // 追蹤最大負（絕對）子陣列和
        int maxAbsSum = 0;    // 儲存找到的最大絕對和

        for (int element : nums) {
            // 更新正數和：如果加上當前元素後小於零，則重設為零
            positiveSum = max(0, positiveSum + element);
            
            // 更新負數和：將元素視為負數，檢查最大負子陣列
            negativeSum = max(0, negativeSum - element);
            
            // 比較並儲存當前正數和、負數和與當前最大絕對和的最大值
            maxAbsSum = max(maxAbsSum, max(positiveSum, negativeSum));
        }

        return maxAbsSum;
    }
};

Python

class Solution:
    def maxAbsoluteSum(self, nums):
        positiveSum = 0  # 跟蹤最大正子陣列和
        negativeSum = 0  # 跟蹤最大負（絕對）子陣列和
        maxAbsSum = 0    # 儲存找到的最大絕對值和

        for element in nums:
            # 更新正和：如果加上當前元素後小於零，則重置為零
            positiveSum = max(0, positiveSum + element)

            # 更新負和：將元素視為負數，檢查最大負子陣列
            negativeSum = max(0, negativeSum - element)

            # 比較並儲存當前正和、負和與目前最大絕對值和中的最大值
            maxAbsSum = max(maxAbsSum, max(positiveSum, negativeSum))

        return maxAbsSum

複雜度分析

• 時間複雜度: $O(n)$

  給定的演算法正好遍歷一次陣列 nums，在迴圈中對每個元素進行恆定量的工作。因此，與輸入陣列 nums 的大小 $n$ 相比，時間複雜度是線性的。

• 空間複雜度: $O(1)$

  該演算法使用恆定量的額外空間，無論輸入大小如何。變數如 positiveSum、negativeSum 和 maxAbsSum 用於儲存中間和最終結果，其空間使用不會隨著輸入陣列 nums 的大小增長。因此，空間複雜度是恆定的。