【算法文章8 | 力扣1749题：动态规划 or 前缀和】

这是力扣的一道1542分的题，可以使用前缀和跟动态规划这两个方法来做：

题目链接：1749. 任意子数组和的绝对值的最大值

方法1：前缀和

思路

这道题要找nums数组中和的绝对值最大的任意子数组，子数组的问题，我们可以使用前缀和的思想来做，假设前缀和数组是s

• 那么子区间的前缀和绝对值可以这样表示：|s[j] - s[i]|
• 我们不难发现，s[j]跟s[i]相差越大，上式也就越大。
• 因此我们只需要找s数组中的最大前缀和跟最小前缀和，然后求差即可：max(s)−min(s)
• 因为存在负数的情况，貌似不好理解，所以可以分两种情况理解，在 s 数组中：
  • 如果最大前缀和出现在最小前缀和的右边，那么上式算的是最大子数组和。
  • 如果最大前缀和出现在最小前缀和的左边，那么上式算的是最小子数组和的绝对值。

还有一个更好理解的方式

就是想象是在爬山，本质上就是在计算最大的高度差：

拿案例1举例：

输入：nums = [1,-3,2,3,-4] 输出：5 

前缀和如图所示：

代码如下

classSolution{publicintmaxAbsoluteSum(int[] nums){int n =nums.length;int s =0;int max =0;int min =0;for(int i =0; i < n; i++){ s+=nums[i];// max = Math.max(max , s);// min = Math.min(min , s);//效率更高的写法if(max < s){ max = s;}elseif(s < min){ min = s;}}return max - min;}}

方法2：动态规划

这道题也可以使用动态规划的写法，这道题属于线性的动态规划

思路

1. 考虑以nums[i]结尾的最大子数组和 （以nums[i]结尾的最小子数组逻辑是一样的）
   • 如果子数组只有自己一个数，那么最大子数组和就是nums[i]
   • 如果跟前面拼接起来，那么就变成了求更小的子问题：求以 nums[i−1] 结尾的最大子数组和
2. 定义状态:
   • 设 f[i] 为以 nums[i] 结尾的最大子数组和。
   • 设 g[i] 为以 nums[i] 结尾的最小子数组和。
3. 状态转移方程：
   • 最大值： f [ i ] = max ⁡ ( f [ i − 1 ] + n u m s [ i ] , n u m s [ i ] ) f[i] = \max(f[i-1] + nums[i], nums[i]) f[i]=max(f[i−1]+nums[i],nums[i])最小值： g [ i ] = min ⁡ ( g [ i − 1 ] + n u m s [ i ] , n u m s [ i ] ) g[i] = \min(g[i-1] + nums[i], nums[i]) g[i]=min(g[i−1]+nums[i],nums[i])
     • 要么接在前面的最大和后面，要么自己重新开始。
   • 意为：要么接在前面的最小和后面，要么自己重新开始。
4. 最终答案：
   • maxSum = max(maxSum, f[i])
   • minSum = min(minSum, g[i])

最后返回： max ⁡ ( m a x S u m , − m i n S u m ) \max(maxSum, -minSum) max(maxSum,−minSum)

代码

classSolution{publicintmaxAbsoluteSum(int[] nums){int n = nums.length;//表示以 nums[i] 结尾的最大子数组和int[]f =newint[n];//表示以 nums[i] 结尾的最小子数组和int[]g =newint[n];//初始化 f[0]= nums[0]; g[0]= nums[0];int ans =Math.abs(nums[0]);for(int i =1; i < n; i++){// 状态转移：要么接上前面的，要么从当前推倒重来 f[i]=Math.max(nums[i],f[i-1]+ nums[i]); g[i]=Math.min(nums[i],g[i-1]+ nums[i]);//当前最大和、当前最小和的绝对值、以及之前的最大绝对值 ans =Math.max(ans,Math.max(f[i],-g[i]));}return ans;}}

这个方法好理解一下，我们也可以更优雅的写法：使用空间优化的方法，如下：

空间优化的写法

因为求 f [ i ] f[i] f[i] 的公式是： f [ i ] = max ⁡ ( n u m s [ i ] , f [ i − 1 ] + n u m s [ i ] ) f[i] = \max(nums[i], f[i-1] + nums[i]) f[i]=max(nums[i],f[i−1]+nums[i])

f[i]只根据前一次的数据f[i-1],至于更早的数据，对于i来说都不需要，所以，我们可以使用滚动变量的方式就行空间优化：

classSolution{publicintmaxAbsoluteSum(int[] nums){// 1. 先显式初始化第一个元素int fMax = nums[0];int fMin = nums[0];int ans =Math.abs(nums[0]);// 2. 从 i = 1 开始循环for(int i =1; i < nums.length; i++){int x = nums[i]; fMax =Math.max(x, fMax + x); fMin =Math.min(x, fMin + x); ans =Math.max(ans,Math.max(fMax,-fMin));}return ans;}}

或者：

• 不使用空间优化时，状态转移方程是： f [ i ] = max ⁡ ( n u m s [ i ] , f [ i − 1 ] + n u m s [ i ] ) f[i] = \max(nums[i], f[i-1] + nums[i]) f[i]=max(nums[i],f[i−1]+nums[i])
• 这个方程可以提取出 n u m s [ i ] nums[i] nums[i]，写成： f [ i ] = max ⁡ ( 0 , f [ i − 1 ] ) + n u m s [ i ] f[i] = \max(0, f[i-1]) + nums[i] f[i]=max(0,f[i−1])+nums[i]

所以当你使用空间优化，把数组 f[i] 变成变量 fMax 时，代码可以写成：

fMax =Math.max(fMax,0)+ x;

且在第一轮循环结束后，fMax 和 fMin 都会被“强制校准”为数组的第一个元素

classSolution{publicintmaxAbsoluteSum(int[] nums){int ans =0, fMax =0, fMin =0;for(int x : nums){ fMax =Math.max(fMax,0)+ x; fMin =Math.min(fMin,0)+ x; ans =Math.max(ans,Math.max(fMax,-fMin));}return ans;}}

如果你觉得有帮助，欢迎点赞收藏！