諸神緘默不語-個(gè)人CSDN博文目錄
力扣刷題筆記

1. 暴力搜索

直接用2個(gè)指針從索引0開始找到最后一個(gè)索引，時(shí)間復(fù)雜度大概是$O(n^2)$吧，總之這么搞不行，以下是我用Python寫的一些典型失敗案例

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_abs=0
        nums_len=len(nums)
        for pointer1 in range(nums_len):
            for pointer2 in range(pointer1,nums_len):
                sub_nums=nums[pointer1:pointer2+1]
                max_abs=max(max_abs,abs(sum(sub_nums)))
        return max_abs

↑會(huì)超時(shí)，這個(gè)我覺得應(yīng)該是sum()的問題，所以做了改進(jìn)：

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        sum_table=[[0 for _ in range(len(nums))] for _ in range(len(nums))]
        for i in range(len(nums)):
            sum_table[i][i]=nums[i]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                sum_table[i][j]=sum_table[i][j-1]+nums[j]
        max_abs=0
        for i in sum_table:
            for j in i:
                max_abs=max(max_abs,abs(j))
        return max_abs

↑這個(gè)又會(huì)爆內(nèi)存，我罵罵咧咧。
這個(gè)我一開始猜是因?yàn)?太多了，所以把所有一直都是0的部分給刪除了：

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        sum_table=[[0 for _ in range(len(nums)-i)] for i in range(len(nums))]
        for i in range(len(nums)):
            sum_table[i][0]=nums[i]
        for i in range(len(nums)):
            for j in range(1,len(nums)-i):
                sum_table[i][j]=sum_table[i][j-1]+nums[j+i]
        max_abs=0
        for i in sum_table:
            for j in i:
                max_abs=max(max_abs,abs(j))
        return max_abs

↑還是會(huì)爆內(nèi)存
繼續(xù)縮：

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_abs=0
        for i in range(len(nums)):
            pre_sum=nums[i]
            max_abs=max(max_abs,abs(pre_sum))
            for j in range(i+1,len(nums)):
                pre_sum=pre_sum+nums[j]
                max_abs=max(max_abs,abs(pre_sum))
        return max_abs

這回超時(shí)了

2. 動(dòng)態(tài)規(guī)劃

然后我就去看題解了。

來自官方題解：https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/solutions/2372374/ren-yi-zi-shu-zu-he-de-jue-dui-zhi-de-zu-qerr/

在一組數(shù)字中絕對(duì)值的最大值，可能是最大的值的絕對(duì)值，也可能是最小值的絕對(duì)值。
所以找子數(shù)組和絕對(duì)值的最大值，就要找最大的子數(shù)組和，和最小的子數(shù)組和。
所以解決方案是分別計(jì)算這兩種情況：在找最大的子數(shù)組和時(shí)，遍歷數(shù)組，保留到上一個(gè)數(shù)字為止的全局子數(shù)組最大和global_max+有上一個(gè)數(shù)字在的子數(shù)組的最大和sumable_max或者0（0的意思就是甩掉上一個(gè)數(shù)字），如果新數(shù)字+sumable_max比positiveMax還高，就更新global_max；如果這個(gè)數(shù)字加進(jìn)sumable_max大于0了，那對(duì)后續(xù)數(shù)字而言，加sumable_max是可以更大的（我在說什么，反正就是這個(gè)意思），否則不如直接重開。
找最小的子數(shù)組和時(shí)就完全反過來：保留全局最小和global_min+可加最小和sumable_min或0，如果新數(shù)字+sumable_min<global_min就更新global_min；如果新數(shù)字+sumable_min>0那就白給，立刻重開。

時(shí)間復(fù)雜度$O(n)$，空間復(fù)雜度$O(1)$

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        global_max=0
        sumable_max=0
        global_min=0
        sumable_min=0
        for i in nums:
            sumable_max+=i
            global_max=max(global_max,sumable_max)
            sumable_max=max(0,sumable_max)
            
            sumable_min+=i
            global_min=min(global_min,sumable_min)
            sumable_min=min(0,sumable_min)
        return max(abs(global_max),abs(global_min))

官方Java代碼：

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int positiveMax = 0, negativeMin = 0;
        int positiveSum = 0, negativeSum = 0;
        for (int num : nums) {
            positiveSum += num;
            positiveMax = Math.max(positiveMax, positiveSum);
            positiveSum = Math.max(0, positiveSum);
            negativeSum += num;
            negativeMin = Math.min(negativeMin, negativeSum);
            negativeSum = Math.min(0, negativeSum);
        }
        return Math.max(positiveMax, -negativeMin);
    }
}

3. 前綴和

前綴和指的是在數(shù)組最前面加個(gè)0，從第1個(gè)數(shù)字到當(dāng)前數(shù)字的和，任何子數(shù)組和顯然都是某2個(gè)前綴和的差值，最大的子數(shù)組和絕對(duì)值顯然就是最大前綴和-最小前綴和（如果最小值<0就直接是最大值-最小值，如果最小值>0就用那個(gè)0）

Python 3有內(nèi)置函數(shù)：

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        s = list(accumulate(nums, initial=0))  # nums 的前綴和
        return max(s) - min(s)

Java實(shí)現(xiàn)的示例：文章來源地址http://www.zghlxwxcb.cn/news/detail-638093.html

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n=nums.length;
        int pre=0;
        int max=0;
        int min=0;
        for(int i=0;i<n;i++){
            pre+=nums[i];
            max=Math.max(max,pre);
            min=Math.min(min,pre);
        }
        return max-min;
    }
}

到了這里，關(guān)于1749. 任意子數(shù)組和的絕對(duì)值的最大值的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！