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;
    }
}
from typing import List

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

        result = float('-inf')
        for i in range(1, len(arr)):
            dp[i][0] = arr[i] + max(0, dp[i - 1][0])
            dp[i][1] = arr[i] * arr[i] + max(0, dp[i - 1][0])
            dp[i][2] = arr[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]))

All Problems

All Solutions