Maximum Subarray Sum with One Square Allowed
Problem Overview
At most one element may be replaced by its square, and the answer is the largest sum of a contiguous block after that choice.
Intuition
At most one element may be replaced by its square, and the answer is the largest sum of a contiguous block after that choice. A block that ends at the current index has two forms worth keeping. The plain form has squared nothing. It is the current value alone, or that value added to the best plain form that ended on the previous index. The squared form has already used its one square. It can start fresh at the square of the current value, extend a plain form by that square, or extend an earlier squared form by the current value left as it is. Those three choices put the square on the current element as a new start, on the current element after a plain prefix, or somewhere earlier in the block. The best value among every plain form and every squared form is the answer. Only those two running sums are stored, so the extra memory stays constant. Both sums stay in 64 bit integers, because the square of a large element overflows a 32 bit product.
Algorithm
- 1Start the plain sum at the first value and the squared sum at the square of that value.
- 2For each later value, save both of the previous sums first.
- 3Set the next plain sum to the value itself, or to the previous plain sum plus the value.
- 4Set the next squared sum to the square, to the previous plain sum plus the square, or to the previous squared sum plus the value.
- 5Keep the larger of the answer and the two new sums, then return the answer.
Example Walkthrough
Input: arr = [-4, -4, -2, 5, 2, -1]
- 1. The squares of the opening negative values are 16, 16, and 4.
- 2. At 5 the squared form becomes 25, which is a block that starts on that square.
- 3. Adding the following 2 extends that form to 27.
- 4. The block {5, 2} with 5 squared is 25 plus 2, and that is the best sum.
Output: 27
Common Pitfalls
- • Build the squared form from the previous plain sum before that plain sum is replaced. The new plain sum already contains the current value.
- • When a running sum is negative, the next form starts at the current value or at its square.
- • The square of a large element does not fit in a 32 bit product. Both running sums stay in 64 bit integers.
- • An empty array has no block to score. The method returns 0.
// Approach: A subarray ending at the current index has two useful forms.
// One has squared nothing, and one has already squared a single element.
// The plain form is the current value, or that value added to the previous
// plain form. The squared form starts at the square of the current value,
// extends a plain form by that square, or extends a squared form by the
// current value. The best of every form is the answer.
// Complexity: O(n) time, O(1) extra space.
class Solution {
public int maximumSubarray(int[] arr) {
int n = arr.length;
if (n == 0)
return 0;
long plain = arr[0];
long squared = (long) arr[0] * arr[0];
long best = Math.max(plain, squared);
for (int i = 1; i < n; i++) {
long value = arr[i];
long square = value * value;
long nextPlain = Math.max(value, plain + value);
long nextSquared = Math.max(square, Math.max(plain + square, squared + value));
plain = nextPlain;
squared = nextSquared;
best = Math.max(best, Math.max(plain, squared));
}
return (int) best;
}
}