Maximum Subarray Sum with Single Element Doubling — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, you must choose exactly one element and double its value. After performing this operation, find the maximum possible sum of a non-empty subarray.
Examples
Input
[1, 3, -2]
Output
5
Explanation: Step-by-step: with input [1, 3, -2], we double the element at index 0 (value 1) to get [2, 3, -2]. The maximum possible sum of a non-empty subarray after doubling one element is 2 + 3 = 5.
Input
[2, -1, 4, 8]
Output
21
Explanation: Step-by-step: with input [2, -1, 4, 8], we double the element at index 3 (value 8) to get [2, -1, 4, 16]. The maximum possible sum of a non-empty subarray after doubling one element is 2 + (-1) + 4 + 16 = 21.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Optimal Approach & Strategy
Use dynamic programming to track two states: the max subarray ending at i without a doubled element and the max subarray ending at i with exactly one doubled element. This single-pass scan provides the answer in linear time.
Brute Force Approach
Iterate through every index of the array, create a copy where that element is doubled, and run Kadane's algorithm to find the maximum subarray sum. This approach checks every possible doubling scenario individually.
Verified 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.