Welcome to Subscribe On Youtube

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

1746. Maximum Subarray Sum After One Operation

Level

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 {
    #[allow(dead_code)]
    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
    }
}

All Problems

All Solutions