LeetCode 动态规划 任意子数组和的绝对值的最大值

任意子数组和的绝对值的最大值

给你一个整数数组 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

题解

首先来一个错误的思路

错误思路

对于每一个数组的元素，它只有成为前面的子数组的一部分或者成为另一个新数组的开头这两种选择

只需要选这两种选择中执行后绝对值更大的就行了

错误原因

举个例子

数组[8,-2,-6,-1,-10]

显然最大和的绝对值子数组为-2,-6,-1,-10

但是依据上述思路，对于-2这个数据，加上前面的8之后的绝对值更大，我们就将8加上

但是加上8之后导致后面的计算就无法取到最大的子数组值

换句话说

最大的绝对值是最大的正或最小的负

上诉思路中，对于每一个元素我们都选择了最大的正或最小的负中的一个

这样就导致后面的数据进行选择的时候少了一种可能

所以不能按照当前数据与以前面数据结尾的子数组的绝对值的最大值进行比较从而得出结果的思路

因为对于绝对值是需要在最大的正与最小的负中选择的

以前面数据结尾的子数组的绝对值的最大值少了其中一种情况

求出的结果是不正确的

正确的思路应当是比较以前面数据结尾的子数组的最大值与最小值

判断是否加上最大或最小这两种情况之后选择其中绝对值最大的

正确思路

对于绝对值，我们可以求出子数组和的最大值以及最小值

再选择其中绝对值大的即可

对于求子数组的最大值

我们可以将问题拆分为

对于一个数据，它只有加入以前一个数据结尾的子数组或者不加入成为新的开头

如果以前一个数据结尾的子数组的和是负的，显然应当不加入成为新的开头

否则加入以前一个数据结尾的子数组

每一个数据选择后的最大值就是子数组的最大值

求最小值同理

最后选择其中绝对值大的

代码如下

int maxAbsoluteSum(int* nums, int numsSize) {
    int res=abs(nums[0]);
    int max=nums[0];
    int min=nums[0];
    for(int i=1;i<numsSize;i++)
    {
        if(max>0)
        {
            max+=nums[i];
        }
        else
        {
            max=nums[i];
        }
        if(min<0)
        {
            min+=nums[i];
        }
        else
        {
            min=nums[i];
        }
        int n=max>-min?max:-min;
        if(n>res)
        {
            res=n;
        }
    }
    return res;
}