LC.P1749[任意子数组和的绝对值的最大值]

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length, ans = Math.abs(nums[0]);
        int[] f = new int[n], g = new int[n];
        f[0] = nums[0];
        g[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            f[i] = Math.max(f[i - 1], 0) + nums[i];
            g[i] = Math.min(g[i - 1], 0) + nums[i];
            ans = Math.max(ans, Math.max(f[i], Math.abs(g[i])));
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int ans = 0, fMax = 0, fMin = 0;
        for (int num : nums) {
            fMax = Math.max(fMax, 0) + num;
            fMin = Math.min(fMin, 0) + num;
            ans = Math.max(ans, Math.max(fMax, Math.abs(fMin)));
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$