Formatted question description: https://leetcode.ca/all/1746.html

1746. Maximum Subarray Sum After One Operation

Medium

Description

You are given an integer array nums. You must perform exactly one operation where you can replace one element nums[i] with nums[i] * nums[i].

Return the maximum possible subarray sum after exactly one operation. The subarray must be non-empty.

Example 1:

Input: nums = [2,-1,-4,-3]

Output: 17

Explanation: You can perform the operation on index 2 (0-indexed) to make nums = [2,-1,16,-3]. Now, the maximum subarray sum is 2 + -1 + 16 = 17.

Example 2:

Input: nums = [1,-1,1,1,-1,-1,1]

Output: 4

Explanation: You can perform the operation on index 1 (0-indexed) to make nums = [1,1,1,1,-1,-1,1]. Now, the maximum subarray sum is 1 + 1 + 1 + 1 = 4.

Constraints:

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

Solution

Use dynamic programming. Let n be the length of nums. Create a 2D array dp of n rows and 3 columns, where

• dp[i][0] represents the maximum subarray sum that ends at index i when no operation is performed,
• dp[i][1] represents the maximum subarray sum that ends at index i when the one operation is performed at index i, and
• dp[i][2] represents the maximum subarray sum that ends at index i when the one operation is performed before index i.

Initially, dp[0][0] = nums[0], dp[0][1] = nums[0] * nums[0] and dp[0][2] = Integer.MIN_VALUE, which means dp[0][2] is an impossible value.

Loop over i from 1 to n - 1. For each i, there is dp[i][0] = Math.max(dp[i - 1][0], 0) + nums[i], dp[i][1] = Math.max(dp[i - 1][0], 0) + nums[i] * nums[i] and dp[i][2] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), 0) + nums[i].

Finally, return the maximum value in the last two columns of dp.

• class Solution {
public int maxSumAfterOperation(int[] nums) {
int length = nums.length;
int[][] dp = new int[length][3];
dp[0][0] = nums[0];
dp[0][1] = nums[0] * nums[0];
dp[0][2] = Integer.MIN_VALUE;
int max = dp[0][1];
for (int i = 1; i < length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], 0) + nums[i];
dp[i][1] = Math.max(dp[i - 1][0], 0) + nums[i] * nums[i];
dp[i][2] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), 0) + nums[i];
int curMax = Math.max(dp[i][1], dp[i][2]);
max = Math.max(max, curMax);
}
return max;
}
}

class Solution {
public int maxSumAfterOperation(int[] nums) {
int f = 0, g = 0;
int ans = Integer.MIN_VALUE;
for (int x : nums) {
int ff = Math.max(f, 0) + x;
int gg = Math.max(Math.max(f, 0) + x * x, g + x);
f = ff;
g = gg;
ans = Math.max(ans, Math.max(f, g));
}
return ans;
}
}

//////

class Solution {
public int maxSumAfterOperation(int[] nums) {
int f = 0, g = 0;
int ans = Integer.MIN_VALUE;
for (int x : nums) {
int ff = Math.max(f, 0) + x;
int gg = Math.max(Math.max(f, 0) + x * x, g + x);
f = ff;
g = gg;
ans = Math.max(ans, Math.max(f, g));
}
return ans;
}
}

• class Solution {
public:
int maxSumAfterOperation(vector<int>& nums) {
int f = 0, g = 0;
int ans = INT_MIN;
for (int x : nums) {
int ff = max(f, 0) + x;
int gg = max(max(f, 0) + x * x, g + x);
f = ff;
g = gg;
ans = max({ans, f, g});
}
return ans;
}
};

• from typing import List

class Solution:
def maximumSum(self, nums: List[int]) -> int:
dp = []
dp = [[0]*3 for i in range(len(nums))]
dp[0][0] = nums[0]
dp[0][1] = nums[0] * nums[0]
dp[0][2] = float('-inf')

result = float('-inf')
for i in range(1, len(nums)):
dp[i][0] = nums[i] + max(0, dp[i - 1][0])
dp[i][1] = nums[i] * nums[i] + max(0, dp[i - 1][0])
dp[i][2] = nums[i] + max(0, dp[i - 1][1], dp[i - 1][2])

result = max(result, dp[i][0], dp[i][1], dp[i][2])

return result

if __name__ == "__main__":
print(Solution().maximumSum([2,-1,-4,-3]))

###########

class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
f = g = 0
ans = -inf
for x in nums:
ff = max(f, 0) + x
gg = max(max(f, 0) + x * x, g + x)
f, g = ff, gg
ans = max(ans, f, g)
return ans


• func maxSumAfterOperation(nums []int) int {
var f, g int
ans := -(1 << 30)
for _, x := range nums {
ff := max(f, 0) + x
gg := max(max(f, 0)+x*x, g+x)
f, g = ff, gg
ans = max(ans, max(f, g))
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• impl Solution {
pub fn max_sum_after_operation(nums: Vec<i32>) -> i32 {
// Here f[i] represents the value of max sub-array that ends with nums[i] with no substitution
let mut f = 0;
// g[i] represents the case with exact one substitution
let mut g = 0;
let mut ret = 1 << 31;

// Begin the actual dp process
for e in &nums {
// f[i] = MAX(f[i - 1], 0) + nums[i]
let new_f = std::cmp::max(f, 0) + *e;
// g[i] = MAX(MAX(f[i - 1], 0) + nums[i] * nums[i], g[i - 1] + nums[i])
let new_g = std::cmp::max(std::cmp::max(f, 0) + *e * *e, g + *e);
// Update f[i] & g[i]
f = new_f;
g = new_g;
// Since we start at 0, update answer after updating f[i] & g[i]
ret = std::cmp::max(ret, g);
}

ret
}
}