LeetCode Solutions Blog

Maximum Subarray Sum After One Operation

Number: 1893

Difficulty: Medium

Paid? Yes

Companies: Sprinklr

Problem Description

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 applying the operation exactly once. The subarray must be non-empty.

Key Insights

We can use dynamic programming with two states:
- One state for the maximum sum ending at index i without using the operation.
- Another state for the maximum sum ending at index i where the operation has already been applied.
At every index, decide whether to:
- Start a new subarray.
- Extend the previous subarray.
- Use the operation on the current element and either start fresh or extend a previous subarray that has not used the operation.
The answer is the maximum over all subarrays that have exactly one operation applied.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (Can be optimized to O(1) using rolling variables)

Solution

We solve this problem using two dynamic programming arrays: dp_no_op and dp_op.

dp_no_op[i] is the maximum subarray sum ending at index i without using the squaring operation.
dp_op[i] is the maximum subarray sum ending at index i after the operation has been applied exactly once.

The recurrence relations are as follows:

dp_no_op[i] = max(nums[i], dp_no_op[i-1] + nums[i])
dp_op[i] = max(dp_no_op[i-1] + (nums[i])^2, dp_op[i-1] + nums[i], (nums[i])^2)

The final answer is the maximum value in dp_op over all indices.

Code Solutions

# Python solution using dynamic programming

def maximumSum(nums):
    n = len(nums)
    # dp_no_op[i]: maximum subarray sum ending at i without using the operation
    # dp_op[i]: maximum subarray sum ending at i with the operation applied exactly once
    dp_no_op = [0] * n  
    dp_op = [0] * n
    
    dp_no_op[0] = nums[0]                 # Base case: using no operation
    dp_op[0] = nums[0] * nums[0]          # Base case: applying operation at index 0
    
    result = dp_op[0]                     # Initialize result with the first op applied value
    
    for i in range(1, n):
        # Maximum subarray ending at i without operation
        dp_no_op[i] = max(nums[i], dp_no_op[i-1] + nums[i])
        
        # Maximum subarray ending at i with exactly one operation used:
        # Option 1: Use the operation on current element and join with previous no op subarray
        # Option 2: Extend previous op-applied subarray by adding current element normally
        # Option 3: Start a new subarray at i with the operation applied on nums[i]
        dp_op[i] = max(dp_no_op[i-1] + nums[i]*nums[i],
                       dp_op[i-1] + nums[i],
                       nums[i]*nums[i])
        
        result = max(result, dp_op[i])
        
    return result

# Example usage:
nums = [2, -1, -4, -3]
print(maximumSum(nums))  # Expected output: 17