2023-08-08每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

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

示例 2：

提示：

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

四、解题代码

class Solution {
public:int maxAbsoluteSum(vector<int>& nums) {int n = nums.size();int dp1[n+5];int dp2[n+5];int max0 = nums[0];int min0 = nums[0];memset(dp1, 0, sizeof(dp1));memset(dp2, 0, sizeof(dp2));dp1[0] = nums[0];dp2[0] = nums[0];for(int i = 1; i < n; ++i){dp1[i] = max(nums[i], dp1[i-1] + nums[i]);dp2[i] = min(nums[i], dp2[i-1] + nums[i]);max0 = max(dp1[i], max0);min0 = min(dp2[i], min0);}return max(abs(max0), abs(min0));}
};

五、解题思路

(1) 采用一维DP的思路解决问题。