丽泽桥网站建设脚本外链生成工具

思路：dp

说到绝对值，大家肯定不陌生，但是用在dp上就会使问题变得稍微复杂一些了。

我们在最大子数组和的那道题中知道，在状态转移的时候，我们会舍弃掉为负数的连续部分，重新构建连续的子串。但是，这里不一样，我们并不能轻易舍弃负数的部分，负数也可能让这个子数组和的绝对值变成最大的，例如0，-1000，1，2这个序列就很典型，我们如果按照上一个题那样做，就会使最大值变成3，而不是1000。

这里给出的思路，就是把最大子数组和与最小子数组和之间，两者分别取绝对值，然后比较谁大这个思路，这样就能考虑到最大子数组和中没有考虑到的把负数加进来的讨论了。

这里用了两个dp数组，一个代表最大子数组和，一个代表最小子数组和。

上代码：

class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {vector<int>dp1(nums.size()+1,0);vector<int>dp2(nums.size()+1,0);dp1[0]=nums[0];dp2[0]=nums[0];int ans=max(abs(dp1[0]),abs(dp2[0]));for(int i=1;i<nums.size();i++){if(dp1[i-1]<=0)dp1[i]=nums[i];if(dp2[i-1]<=0)dp2[i]=dp2[i-1]+nums[i];if(dp1[i-1]>0)dp1[i]=nums[i]+dp1[i-1];if(dp2[i-1]>0)dp2[i]=nums[i];ans=max(ans,max(abs(dp1[i]),abs(dp2[i])));}return ans;}
};