Is Maximum Subarray Sum After One Operation easy or hard?

The problem is classified as Medium. It requires recognizing that the square operation creates two dynamic states and adapting Kadane’s algorithm accordingly. Once the DP transition is identified, the implementation becomes straightforward.

Maximum Subarray Sum After One Operation Python/Java solution

Implement a Kadane-style dynamic programming loop that tracks two values: the best subarray sum without using the operation and the best sum after using it. The same logic works across Python, Java, C++, Go, and Rust with O(n) time and constant space.

How to solve Maximum Subarray Sum After One Operation in O(n)?

Maintain two running values while iterating through the array: one for subarrays that have not used the operation and another for those that already squared an element. Update them using Kadane-style transitions that consider extending the subarray or applying the square at the current index. Track the maximum value seen in the state where the operation has been used.

What is the best approach for Maximum Subarray Sum After One Operation?

The best approach uses dynamic programming with two states, extending Kadane’s algorithm. Track the maximum subarray ending at each index with and without using the square operation. This method processes the array once, giving O(n) time complexity and O(1) space.

Is Maximum Subarray Sum After One Operation asked at Google/Amazon/Meta?

This problem represents a classic dynamic programming variation of the maximum subarray problem. Similar patterns frequently appear in interviews at companies like Amazon, Google, and Meta where candidates must modify Kadane’s algorithm to handle an additional constraint or operation.

What data structure is used in Maximum Subarray Sum After One Operation?

The solution primarily uses dynamic programming with constant variables rather than complex data structures. The array is processed sequentially while maintaining two DP states representing whether the square operation has been applied.

What is the time complexity of Maximum Subarray Sum After One Operation?

The optimal solution runs in O(n) time because each element is processed exactly once while updating two DP states. Only constant extra memory is required, so the space complexity is O(1).

Description Hints 3 Solution Video 13:32

1746. Maximum Subarray Sum After One Operation

Medium65.2% acceptance1 companyPremium elsewhere, free here

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⁵
-10⁴ <= nums[i] <= 10⁴

Asked at 1 company

Sprinklr

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Think about dynamic programming

Hint 2

Define an array dp[nums.length][2], where dp[i][0] is the max subarray sum including nums[i] and without squaring any element.

Hint 3

dp[i][1] is the max subarray sum including nums[i] and having only one element squared.

13:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution