Maximum Subarray Sum with Single Element Doubling — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Maximum subarray sum
O(n)O(1)Problem Description
You are provided with an integer array nums. You are permitted to perform exactly one operation: select a single element at any index i and replace its value with 2 * nums[i]. After this modification, determine the maximum possible sum of any non-empty contiguous subarray within the resulting array.
Your task is to compute this maximum subarray sum efficiently. The solution must account for the fact that the doubling operation can be applied to any element, including those outside the optimal subarray, but only the effect on the chosen subarray matters for the final sum calculation.
Return the maximum sum achievable under these conditions.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Subarray Sum with Single Element Doubling"
WHY DOES IT MATTER?
This pattern extends classic DP on subarrays to incorporate a single-use operation, a common interview motif that tests understanding of state augmentation and optimal substructure.
OPTIMIZATION CHALLENGE
The key insight is to track two mutually exclusive states (double used vs. not used) while scanning once, turning an O(n^2) brute force into O(n) by exploiting overlapping subproblems.
REAL-WORLD CONNECTION
Think of a streaming data pipeline where you can boost the weight of exactly one event (e.g., a high‑priority transaction) before computing rolling aggregates; the algorithm decides where to apply that boost for maximal impact.
Initialize your DP variables with negative infinity for the "with double" state until you actually apply the operation; this prevents accidental reuse of the double and simplifies edge‑case handling.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The classic maximum subarray problem is solved by Kadane's algorithm, which runs in linear time by maintaining the best subarray ending at each position. Introducing a single element doubling operation changes the state space: for each index we must consider two scenarios – the subarray has not used the doubling yet, or it has already used it. A naïve solution would recompute the maximum subarray for every possible doubled index, leading to O(n^2) time, which is infeasible for large n. By extending Kadane's DP to keep two parallel DP arrays – one for "no double used" and one for "double already used" – we can propagate optimal sums in a single left‑to‑right pass, achieving O(n) time and O(1) extra space.
The DP recurrence is:
noDouble[i] = max(nums[i], noDouble[i-1] + nums[i])
withDouble[i] = max(2*nums[i], noDouble[i-1] + 2*nums[i], withDouble[i-1] + nums[i])
The first term of withDouble[i] represents starting a new subarray where the current element is the doubled one, the second term attaches the doubled element to a subarray that hasn't used the operation yet, and the third term extends a subarray that already consumed its double. The answer is the maximum value seen across both DP arrays.
This formulation avoids recomputation, leverages the optimal substructure of subarray sums, and respects the constraint of using the doubling exactly once, delivering an optimal linear‑time solution.
Interview Questions on This Problem
Q1How would you modify Kadane's algorithm to handle exactly one element being doubled in the subarray?
Maintain two DP variables: bestWithout (max subarray sum ending at i without using the double) and bestWith (max subarray sum ending at i having used the double). Update bestWithout with the classic Kadane recurrence, and update bestWith by considering three options – start a new subarray with the doubled current element, extend bestWithout by doubling the current element, or extend bestWith by adding the current element unchanged. Track the global maximum across both.
Q2What is the time and space complexity of the optimal solution, and why can't we achieve better than O(n) time?
The optimal solution runs in O(n) time and O(1) extra space because we must examine each element at least once to decide whether to double it or not, and the DP recurrences only need constant‑size state. Any algorithm that skips elements would miss potential optimal subarrays, so linear time is a lower bound.
Q3If the array length is 1, how does the algorithm behave and what is the answer?
When n = 1, the only possible subarray is the single element itself, which must be doubled per the problem statement. The answer is 2 * nums[0]. The DP initialization should handle this edge case by setting both bestWithout and bestWith to the appropriate values.
Examples
Input
nums = [1, 2, 3, 4]
Output
14
Explanation: The original array is [1, 2, 3, 4]. If we double the element 4 (index 3), the array becomes [1, 2, 3, 8]. The maximum subarray sum is the sum of the entire array: 1 + 2 + 3 + 8 = 14. Other choices yield lower sums (e.g., doubling 3 gives [1, 2, 6, 4] with max sum 13).
Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output
11
Explanation: The optimal subarray in the original array is [4, -1, 2, 1] with sum 6. By doubling the element 4 (index 3), the subarray becomes [8, -1, 2, 1] with sum 10. However, consider doubling the element 2 (index 5) within the subarray [4, -1, 2, 1]. The subarray becomes [4, -1, 4, 1] with sum 8. Wait, let's re-evaluate. The standard Kadane's algorithm finds max subarray. If we double the largest positive element in the best subarray, we maximize the gain. The best subarray is [4, -1, 2, 1] sum=6. Doubling 4 gives 8-1+2+1=10. Doubling 2 gives 4-1+4+1=8. Doubling 1 gives 4-1+2+2=7. Is there a better subarray? What if we include -5? No. What if we double an element outside? No. Let's check [4, -1, 2, 1, -5, 4]. Sum is 5. Doubling 4 (last) gives 4-1+2+1-5+8=9. Doubling 4 (first) gives 8-1+2+1-5+4=9. The maximum is indeed 10? Let's check if a different subarray is better. [2, 1, -5, 4] sum 2. Doubling 4 gives 2+1-5+8=6. The subarray [4, -1, 2, 1] is the best. Max sum with doubling is 10. Wait, let me re-calculate. 4+(-1)+2+1 = 6. Double 4 -> 8. Sum = 8-1+2+1 = 10. Double 2 -> 4. Sum = 4-1+4+1 = 8. Double 1 -> 2. Sum = 4-1+2+2 = 7. Double -1 -> -2. Sum = 4-2+2+1 = 5. So 10 is the max for this subarray. Is there a subarray with higher potential? [1, -3, 4, -1, 2, 1, -5, 4] sum 3. No. The answer is 10.
Input
nums = [5, 5, 5]
Output
15
Explanation: The array is [5, 5, 5]. The maximum subarray is the entire array with sum 15. If we double any element, say the first one, the array becomes [10, 5, 5]. The sum of the entire array is 10 + 5 + 5 = 20. If we double the middle one, [5, 10, 5], sum is 20. If we double the last one, [5, 5, 10], sum is 20. Thus, the maximum sum is 20.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The answer is guaranteed to fit in a 64-bit integer.
Optimal Approach & Strategy
Perform a single left‑to‑right scan while maintaining two DP values: one for subarrays without a double and one for subarrays that have already used the double. Update both in O(1) per element, yielding O(n) total time.
Brute Force Approach
For each index i, double nums[i], run Kadane's algorithm on the modified array, and keep the best result; repeat for all i. This requires O(n^2) time because Kadane is O(n) and we repeat it n times.
Code Solutions
function maximumSubarraySumWithSingleElementDoubling(nums) {
let maxVal = -Infinity;
for (let i = 0; i < nums.length; i++) {
let dp0 = nums[i];
let dp1 = nums[i] * 2;
maxVal = Math.max(maxVal, dp0, dp1);
for (let j = i + 1; j < nums.length; j++) {
dp0 = Math.max(nums[j], dp0 + nums[j]);
dp1 = Math.max(dp1, Math.max(dp0 + nums[j], dp0 + nums[j] * 2));
maxVal = Math.max(maxVal, dp0, dp1);
}
}
return maxVal;
}#include <vector>
#include <algorithm>
class Solution {
public:
int maxSubarraySumWithSingleElementDoubling(std::vector<int>& nums) {
if (nums.empty()) return 0;
long long dp0 = nums[0];
long long dp1 = (long long)nums[0] * 2;
long long res = std::max(dp0, dp1);
for (size_t i = 1; i < nums.size(); ++i) {
long long val = nums[i];
long long next_dp1 = std::max({val * 2, dp0 + val * 2, dp1 + val});
long long next_dp0 = std::max(val, dp0 + val);
dp1 = next_dp1;
dp0 = next_dp0;
res = std::max({res, dp0, dp1});
}
return (int)res;
}
};class Solution {
public int maxSubArraySumWithDoubling(int[] nums) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int subarraySum = 0;
for (int k = i; k <= j; k++) {
subarraySum += nums[k];
}
for (int k = i; k <= j; k++) {
int doubledSubarraySum = subarraySum - nums[k] + 2 * nums[k];
maxSum = Math.max(maxSum, doubledSubarraySum);
}
}
}
return maxSum;
}
}def maxSubArraySumWithDoubling(nums):
n = len(nums)
max_sum = float('-inf')
for i in range(n):
for j in range(i, n):
subarray_sum = sum(nums[i:j+1])
for k in range(i, j+1):
doubled_subarray_sum = sum(nums[i:j+1]) - nums[k] + 2 * nums[k]
max_sum = max(max_sum, doubled_subarray_sum)
return max_sumfunction maximumSubarraySumWithSingleElementDoubling(nums) {
let maxVal = -Infinity;
for (let i = 0; i < nums.length; i++) {
let dp0 = nums[i];
let dp1 = nums[i] * 2;
maxVal = Math.max(maxVal, dp0, dp1);
for (let j = i + 1; j < nums.length; j++) {
dp0 = Math.max(nums[j], dp0 + nums[j]);
dp1 = Math.max(dp1, Math.max(dp0 + nums[j], dp0 + nums[j] * 2));
maxVal = Math.max(maxVal, dp0, dp1);
}
}
return maxVal;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.