Scale Engineer

Maximum Subarray Sum After One Operation

Med
#1599Time: 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.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Sprinklr

Prompt

[Fetch error]

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

  1. Initialize a variable maxSum to the smallest possible integer value.
  2. Use a nested loop to define the start (i) and end (j) of every possible subarray.
  3. For each subarray nums[i...j], calculate its sum, let's call it currentSum.
  4. Update maxSum = max(maxSum, currentSum). This handles the case with no operation.
  5. Iterate through each element k from i to j in the current subarray.
  6. For each element nums[k], calculate the sum if it were squared: sumWithOp = currentSum - nums[k] + nums[k] * nums[k].
  7. Update maxSum = max(maxSum, sumWithOp).
  8. After checking all subarrays and all possible single-element squaring operations, maxSum will 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

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.

← Previous

Previous problem

Next →

Next problem