1749.任意子数组和的绝对值的最大值
题目信息
给你一个整数数组 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
解题思路
这道题使用了动态规划的思想，通过递归和记忆化数组的方式来求解最大绝对和。对于每个位置，通过比较当前元素与前一个位置的最大/最小值之和的方式，来确定在该位置的最大/最小值。最终返回最大绝对和，即最大正数和最小负数之间的较大值。
因为加上了绝对值，除了求最大和之外，还有一种可能是来自最小子数组的和。最后比较两个结果，取最大返回就是结果。
Java代码
public class Solution {
int[] nums,memMax,memMin;
public int maxAbsoluteSum(int[] nums) {
this.nums = nums;
int n = nums.length;
//算最大和，初始化为最小
memMax = new int[n];
Arrays.fill(memMax,Integer.MIN_VALUE / 2);
int mx = Integer.MIN_VALUE / 2;
for (int i = 0 ; i < n; i++) {
mx = Math.max(mx,Max(i));
}
//算最小和，初始化为最大
memMin = new int[n];
Arrays.fill(memMin,Integer.MIN_VALUE / 2);
int mn = Integer.MIN_VALUE / 2;
for (int i = 0 ; i < n; i++) {
mn = Math.min(mn,Min(i));
}
//返回较大的结果。如果mn为正，那一定没有mx大，因为mx是最大和。如果mn为负，那么加上负号就会变为正数，达到绝对值的效果
return Math.max(mx,-mn);
}
//两个DFS
//求最大和
int Max(int i) {
//首先判断 i 是否小于 0，如果是则返回 0。
if (i < 0 ){
return 0;
}
if (memMax[i] != Integer.MIN_VALUE / 2 ) {
return memMax[i];
}
int ans = Max(i - 1);
//如果以i-1结尾的最大的子数组的和为负数，就选择本身。因为如果为负数，加上之后最大和一定会比之前小、就不是最大和了。
return memMax[i] = Math.max(nums[i], nums[i] + (ans > 0 ? ans : 0));
}
//求最小和，可能比最大值要大
int Min(int i) {
if (i < 0) {
return 0;
}
if (memMin[i] != Integer.MIN_VALUE / 2) {
return memMin[i];
}
int ans = Min(i - 1);
//同理，如果小于零，对结果有贡献，就记录，否则就不记录
return memMin[i] = Math.min(nums[i], nums[i] + (ans < 0 ? ans : 0));
}
}