高端设计网站都有哪些,网站权限,编程软件下载手机版,网站建设ahxkj目录
1749. 任意子数组和的绝对值的最大值
题目描述#xff1a;
实现代码与解析#xff1a;
动态规划 分类讨论
原理思路#xff1a;
前缀和
原理思路#xff1a; 1749. 任意子数组和的绝对值的最大值
题目描述#xff1a; 给你一个整数数组 nums 。一个子数组 […目录
1749. 任意子数组和的绝对值的最大值
题目描述
实现代码与解析
动态规划 分类讨论
原理思路
前缀和
原理思路 1749. 任意子数组和的绝对值的最大值
题目描述 给你一个整数数组 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
实现代码与解析
动态规划 分类讨论
class Solution {
public:int maxAbsoluteSum(vectorint nums) {vectorint f(nums.size(), 0); // 以下标 i 结尾的子数组最大值vectorint f2(nums.size(), 0x3f3f3f3f); // 以下标i 结尾的子数组最小值f[0] nums[0];f2[0] nums[0];for (int i 1; i nums.size(); i){f[i] max({f[i - 1] nums[i], nums[i], 0});f2[i] min({f2[i - 1] nums[i], nums[i], 0});}int res 0;for (int i 0; i nums.size(); i){cout f[i] f2[i] endl;int m max(f[i], abs(f2[i]));res max(res, m);}return res;}
};
原理思路 分类讨论一种是情况是取正数一种情况是取负数可以不用数组一样的简单的dp。
前缀和
class Solution {
public:int maxAbsoluteSum(vectorint nums) {int s 0, mx 0, mn 0;for (int i 0; i nums.size(); i) {s nums[i];mx max(mx, s);mn min(mn, s);}return mx - mn;}
};
原理思路 最大值减去最小值就是结果无论最大值在最小值前还是后在前就是负数来的结果在后就是正数得来的结果。
