Maximum Subarray Sum After One Operation
MedPrompt
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible contiguous subarray. For each subarray, it calculates two potential maximums: the sum of the subarray as is, and the sum after squaring one of its elements. By trying to square every element in every subarray, it guarantees finding the maximum possible sum, but at a very high computational cost.
Algorithm
- Initialize a variable
maxSumto the smallest possible integer value. - Use a nested loop to define the start (
i) and end (j) of every possible subarray. - For each subarray
nums[i...j], calculate its sum, let's call itcurrentSum. - Update
maxSum = max(maxSum, currentSum). This handles the case with no operation. - Iterate through each element
kfromitojin the current subarray. - For each element
nums[k], calculate the sum if it were squared:sumWithOp = currentSum - nums[k] + nums[k] * nums[k]. - Update
maxSum = max(maxSum, sumWithOp). - After checking all subarrays and all possible single-element squaring operations,
maxSumwill hold the result.
Walkthrough
The brute-force method systematically explores all possibilities. It uses two nested loops to generate all possible start and end points for a subarray. For each of these subarrays, it first calculates the standard sum. Then, a third loop iterates through the elements of the current subarray, and for each element, it calculates what the subarray sum would be if that specific element were squared. The global maximum sum is updated whenever a larger sum is found.
Here is an optimized version of the brute-force approach that reduces the complexity from O(N^4) to O(N^3) by calculating the subarray sum incrementally.
class Solution { public int maxSumAfterOperation(int[] nums) { int n = nums.length; int maxSum = Integer.MIN_VALUE; // If all numbers are negative, the result is the square of the largest number (least negative) // or the largest number itself. The loop below handles this, but this is a good edge case to consider. // For example, for [-1, -100], max is (-1)^2=1, not -1. for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { currentSum += nums[j]; // Case 1: No operation on subarray nums[i...j] maxSum = Math.max(maxSum, currentSum); // Case 2: One operation on an element within nums[i...j] for (int k = i; k <= j; k++) { int sumWithOp = currentSum - nums[k] + (nums[k] * nums[k]); maxSum = Math.max(maxSum, sumWithOp); } } } return maxSum; }}Complexity
Time
O(N^3), where N is the length of the input array. The three nested loops for `i`, `j`, and `k` lead to cubic complexity.
Space
O(1), as it only uses a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Correct for all inputs, given enough time.
Cons
Highly inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for medium to large inputs.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.