class Solution {
public:
int maxSumAfterOperation(vector<int>& nums) {
}
};
1746. 经过一次操作后的最大子数组和
你有一个整数数组 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 <= 105-104 <= nums[i] <= 104原站题解
golang 解法, 执行用时: 88 ms, 内存消耗: 8 MB, 提交时间: 2023-10-22 10:40:34
func maxSumAfterOperation(nums []int) (ans int) {
x, y := 0, 0
for _, v := range nums {
y = max(0, max(v + y, x + v * v))
x = max(0, x + v)
ans = max(ans, max(x, y))
}
return
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 292 ms, 内存消耗: 26.8 MB, 提交时间: 2023-10-22 10:40:17
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
res=dp0=dp1=-float('inf')
for i in range(len(nums)):
dp1 = max(dp0+nums[i]*nums[i],nums[i]*nums[i],dp1+nums[i])
dp0 = max(dp0+nums[i],nums[i])
res = max(res,dp1,dp0)
return res
java 解法, 执行用时: 7 ms, 内存消耗: 56.3 MB, 提交时间: 2023-10-22 10:39:49
class Solution {
public int maxSumAfterOperation(int[] nums) {
/*
dp[0]:无操作
dp[1]:操作了一次
*/
int []dp = new int[2];
dp[0] = nums[0];
dp[1] = nums[0] * nums[0];
int res = dp[1];
for(int i = 1; i < nums.length; i++){
//贪心策略，如果前面无操作的和小于0，对求最大子数组和是副作用，用0替换。
dp[0] = Math.max(dp[0],0);
//当前操作了一次的最大子数组和为Math.max(前面已经操作了一次再加上当前值,前面无操作+操作当前数)
dp[1] = Math.max(dp[1]+nums[i],dp[0]+nums[i]*nums[i]);
dp[0] = dp[0] + nums[i];
res = Math.max(res,dp[1]);
}
return res;
}
}
java 解法, 执行用时: 5 ms, 内存消耗: 56.1 MB, 提交时间: 2023-10-22 10:39:35
class Solution {
public int maxSumAfterOperation(int[] nums) {
int dp1 = 0 , dp2 = 0 , max = 0;
for(int i = 0 ; i < nums.length ; i++){
dp1 = Math.max(dp1+nums[i] , dp2+nums[i]*nums[i]);//记录平方后的最大值
dp2 = Math.max(nums[i]+dp2 , 0);//记录平方前的最大值
max = Math.max(dp1 , max);
}
return max;
}
}