贵阳网站建设托管,长沙app下载,开网店做代理的公司网站,深圳企业网站制作设计目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣 描述
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 ... 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(23) abs(5) 5 。示例 2
输入nums [2,-5,1,-4,3,-2]
输出8
解释子数组 [-5,1,-4] 和的绝对值最大为 abs(-51-4) abs(-8) 8 。提示
1 nums.length 105-104 nums[i] 104 解题思路
/**
* 1749. 任意子数组和的绝对值的最大值
* 1,-3,2,3,-4
* 2,-5,1,-4,3,-2
* 解题思路
* 动态规划构建2个数组dp1和dp2dp1[i]代表数组右区间为i位可能的最大的正数数组和dp2[i]则为负数。
* 遍历的时候如果nums[i1] dp1[i]0则dp1[i1]nums[i1] dp1[i]否则dp1[i1]0。dp2也是一样的逻辑。
* 找dp1和dp2最大的绝对值即可。
*/ 代码
class Solution1749
{
public:int maxAbsoluteSum(vectorint nums){vectorint dp1(nums.size());vectorint dp2(nums.size());if (nums[0] 0){dp1[0] nums[0];dp2[0] 0;}else{dp1[0] 0;dp2[0] nums[0];}int absValue max(abs(dp1[0]), abs(dp2[0]));for (int i 1; i nums.size(); i){int value nums[i];if (value 0){dp1[i] value dp1[i - 1];dp2[i] min(value dp2[i - 1], 0);}else{dp1[i] max(value dp1[i - 1], 0);dp2[i] value dp2[i - 1];}absValue max(absValue, max(abs(dp1[i]), abs(dp2[i])));}return absValue;}
};
