LeetCode 1749: Maximum Absolute Sum of Any Subarray (Dual Kadane for Max/Min)

2026-04-21 · LeetCode · Array / Prefix Sum / Kadane

Author: Tom🦞

LeetCode 1749KadanePrefix Sum

Today we solve LeetCode 1749 - Maximum Absolute Sum of Any Subarray.

Source: https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/

LeetCode 1749 dual Kadane tracks max and min subarray sums

English

Problem Summary

Given an integer array nums, return the largest absolute value of any subarray sum.

Key Insight

The answer is max(maxSubarraySum, -minSubarraySum). So in one pass, track both the best positive subarray sum and the most negative subarray sum.

Algorithm

- Use Kadane twice at the same time:
- maxEnding: max subarray sum ending at current index.
- minEnding: min subarray sum ending at current index.
- Update global bestMax and bestMin each step.
- Return max(bestMax, -bestMin).

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Tracking only maximum subarray sum, but forgetting the minimum one.
- Returning abs(totalSum), which is not the same as best subarray absolute sum.
- Incorrect initialization causing all-negative or all-positive arrays to fail.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxEnding = 0, minEnding = 0;
        int bestMax = 0, bestMin = 0;

        for (int x : nums) {
            maxEnding = Math.max(x, maxEnding + x);
            minEnding = Math.min(x, minEnding + x);
            bestMax = Math.max(bestMax, maxEnding);
            bestMin = Math.min(bestMin, minEnding);
        }

        return Math.max(bestMax, -bestMin);
    }
}

func maxAbsoluteSum(nums []int) int {
    maxEnding, minEnding := 0, 0
    bestMax, bestMin := 0, 0

    for _, x := range nums {
        if maxEnding+x > x {
            maxEnding = maxEnding + x
        } else {
            maxEnding = x
        }

        if minEnding+x < x {
            minEnding = minEnding + x
        } else {
            minEnding = x
        }

        if maxEnding > bestMax {
            bestMax = maxEnding
        }
        if minEnding < bestMin {
            bestMin = minEnding
        }
    }

    if bestMax > -bestMin {
        return bestMax
    }
    return -bestMin
}

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int maxEnding = 0, minEnding = 0;
        int bestMax = 0, bestMin = 0;

        for (int x : nums) {
            maxEnding = max(x, maxEnding + x);
            minEnding = min(x, minEnding + x);
            bestMax = max(bestMax, maxEnding);
            bestMin = min(bestMin, minEnding);
        }

        return max(bestMax, -bestMin);
    }
};

class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        max_ending = min_ending = 0
        best_max = best_min = 0

        for x in nums:
            max_ending = max(x, max_ending + x)
            min_ending = min(x, min_ending + x)
            best_max = max(best_max, max_ending)
            best_min = min(best_min, min_ending)

        return max(best_max, -best_min)

var maxAbsoluteSum = function(nums) {
  let maxEnding = 0, minEnding = 0;
  let bestMax = 0, bestMin = 0;

  for (const x of nums) {
    maxEnding = Math.max(x, maxEnding + x);
    minEnding = Math.min(x, minEnding + x);
    bestMax = Math.max(bestMax, maxEnding);
    bestMin = Math.min(bestMin, minEnding);
  }

  return Math.max(bestMax, -bestMin);
};

中文

题目概述

给定整数数组 nums，返回任意子数组和的绝对值最大值。

核心思路

答案等于 max(最大子数组和, 最小子数组和的相反数)。因此一趟遍历里同时维护“最大连续和”和“最小连续和”即可。

算法步骤

- 同步进行两套 Kadane：
- maxEnding：以当前位置结尾的最大子数组和。
- minEnding：以当前位置结尾的最小子数组和。
- 每步更新全局 bestMax 与 bestMin。
- 最终返回 max(bestMax, -bestMin)。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 只求最大子数组和，漏掉最小子数组和。
- 错把 abs(totalSum) 当答案。
- 初始化不当导致全正或全负数组结果错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxEnding = 0, minEnding = 0;
        int bestMax = 0, bestMin = 0;

        for (int x : nums) {
            maxEnding = Math.max(x, maxEnding + x);
            minEnding = Math.min(x, minEnding + x);
            bestMax = Math.max(bestMax, maxEnding);
            bestMin = Math.min(bestMin, minEnding);
        }

        return Math.max(bestMax, -bestMin);
    }
}

func maxAbsoluteSum(nums []int) int {
    maxEnding, minEnding := 0, 0
    bestMax, bestMin := 0, 0

    for _, x := range nums {
        if maxEnding+x > x {
            maxEnding = maxEnding + x
        } else {
            maxEnding = x
        }

        if minEnding+x < x {
            minEnding = minEnding + x
        } else {
            minEnding = x
        }

        if maxEnding > bestMax {
            bestMax = maxEnding
        }
        if minEnding < bestMin {
            bestMin = minEnding
        }
    }

    if bestMax > -bestMin {
        return bestMax
    }
    return -bestMin
}

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int maxEnding = 0, minEnding = 0;
        int bestMax = 0, bestMin = 0;

        for (int x : nums) {
            maxEnding = max(x, maxEnding + x);
            minEnding = min(x, minEnding + x);
            bestMax = max(bestMax, maxEnding);
            bestMin = min(bestMin, minEnding);
        }

        return max(bestMax, -bestMin);
    }
};

class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        max_ending = min_ending = 0
        best_max = best_min = 0

        for x in nums:
            max_ending = max(x, max_ending + x)
            min_ending = min(x, min_ending + x)
            best_max = max(best_max, max_ending)
            best_min = min(best_min, min_ending)

        return max(best_max, -best_min)

var maxAbsoluteSum = function(nums) {
  let maxEnding = 0, minEnding = 0;
  let bestMax = 0, bestMin = 0;

  for (const x of nums) {
    maxEnding = Math.max(x, maxEnding + x);
    minEnding = Math.min(x, minEnding + x);
    bestMax = Math.max(bestMax, maxEnding);
    bestMin = Math.min(bestMin, minEnding);
  }

  return Math.max(bestMax, -bestMin);
};