难度: Medium
给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
请你找出 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 <= nums.length <= 105-104 <= nums[i] <= 104运行时间: 48 ms
内存: 27.8 MB
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
psum = list(accumulate(nums, initial=0))
return max(psum) - min(psum)
题解采用了前缀和的方法来简化最大子数组和的绝对值的查找。首先通过 itertools 的 accumulate 函数计算数组 nums 的前缀和，这样每个元素 psum[i] 表示从 nums[0] 到 nums[i-1] 的和。由于子数组的和可以表示为两个前缀和的差，因此最大的绝对值和可以通过求前缀和数组的最大值和最小值的差来得到。这种方法避免了需要显式地计算每个可能子数组的和，从而提高了效率。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
# 使用 accumulate 计算前缀和，initial=0 使得 psum[0] = 0，对应于前缀和的初始状态
psum = list(accumulate(nums, initial=0))
# 计算前缀和数组中的最大值和最小值，然后求它们的差值
return max(psum) - min(psum)
使用前缀和的方法可以将问题的时间复杂度从 O(n^2) 降低到 O(n)。直接遍历所有可能的子数组求解需要两层循环，一层用于确定子数组的起始位置，另一层用于确定子数组的结束位置，并计算每个子数组的和，这是一个时间复杂度很高的操作。相对地，前缀和只需要一次遍历来建立，并可以在常数时间内计算任意子数组的和，大大提高了效率。
子数组的和可以表示为两个前缀和的差，即 sum(nums[i:j]) = psum[j] - psum[i], 其中 0 <= i < j <= n。为了最大化这个差的绝对值，我们需要最大化 psum[j] - psum[i]（当 psum[j] > psum[i]）和最小化 psum[j] - psum[i]（当 psum[j] < psum[i]）。这可以通过计算前缀和数组的最大值和最小值来实现，因此最大的绝对值差即为 max(psum) - min(psum)。
在前缀和数组中加上初始值0是为了方便计算从数组起始到任一位置的子数组和。这样，任一位置 i 的前缀和 psum[i] 实际上表示了从 nums[0] 到 nums[i-1] 的和。如果没有这个初始的0，我们就无法用 psum[j] - psum[i] 的形式来直接计算从数组开始到某个位置的子数组和（即当 i=0 时）。
在Python中，整数类型是动态扩充的，可以处理任意大的整数，因此通常不需要担心整数溢出问题。然而，在其他一些编程语言中，如 Java 或 C++，整数类型有固定的大小（如32位或64位），在这些语言中实现时需要考虑整数溢出的问题。在这种情况下，可能需要使用更大的数据类型或在计算过程中进行模运算来防止溢出。