经过一次操作后的最大子数组和

说在前面

🎈每天进行一道算法题目练习，今天的题目是“经过一次操作后的最大子数组和”。

问题描述

你有一个整数数组 nums。你只能将一个元素 nums[i] 替换为 nums[i] * nums[i]。

返回替换后的最大子数组和。\
示例 1：

输入：nums = [2,-1,-4,-3]
输出：17
解释：你可以把-4替换为16(-4*(-4))，使nums = [2,-1,16,-3]. 现在，最大子数组和为 2 + -1 + 16 = 17.

示例 2：

输入：nums = [1,-1,1,1,-1,-1,1]
输出：4
解释：你可以把第一个-1替换为1，使 nums = [1,1,1,1,-1,-1,1]. 现在，最大子数组和为 1 + 1 + 1 + 1 = 4.

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

思路分析

读完题目我们可以知道，我们需要找出最大的子数组和，并在我们还能对数组元素进行一次操作，将 nums[i] 替换成 nums[i]*nums[i],这与我们之前做过的求数组的最大连续子数组和其实是一样的，只是多了一个替换数组元素的机会。让我们先来回忆一下怎们求数组的最大子连续子数组和。

• 求连续子数组的最大和

每一位置的子数组和与其上一个元素相关，当（上一个元素+当前位置元素）> 当前位置元素时，当前位置元素的最大和为（上一个元素+当前位置元素），也就是说当上一个元素的值大于0时，当前位置的元素的最大值应该是加上上一个位置的元素的和，当然上一个元素的值又和上上个元素的值相关，这样不断往回推，我们很快就可以得出一个动态转移方程：f(i)=max{f(i−1)+nums[i],nums[i]}

let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
    pre = Math.max(pre + x, x);
    maxAns = Math.max(maxAns, pre);
});

• 替换数组元素

可以在求连续子数组的最大和的基础上加多一个变量来保存替换当前位置元素时的最大值，每一位置的最大值有两种可以得到的方式；
（1）当前位置数组元素翻倍 + 上一位置元素不翻倍
（2）当前位置数组元素不翻倍 + 上一位置元素翻倍
我们只需要取这两者中的最大值并不断向后遍历维护即可。

for (let i = 1; i < nums.length; i++) {
    double = Math.max(nums[i] * nums[i] + one, nums[i] * nums[i], nums[i] + double)
    one = Math.max(nums[i] + one, nums[i])
    res = Math.max(res, one, double);
}

AC代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumAfterOperation = function (nums) {
    let one = nums[0];
    let double = nums[0] * nums[0];
    let res = Math.max(one, double)
    for (let i = 1; i < nums.length; i++) {
        double = Math.max(nums[i] * nums[i] + one, nums[i] * nums[i], nums[i] + double)
        one = Math.max(nums[i] + one, nums[i])
        res = Math.max(res, one, double);
    }
    return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。