mediumArraysPattern: Kadane's Algorithm
Maximum Subarray Sum with Single Element Doubling Solution
Problem Statement
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
Example 1:
Input:nums = [1, -2, 3]
Output:6
Explanation: By doubling the element at index 2 (value 3), the array becomes [1, -2, 6]. The maximum subarray sum is 6, achieved by the subarray [6].
Example 2:
Input:nums = [-3, 2, -1, 4]
Output:9
Explanation: By doubling the element at index 3 (value 4), the array becomes [-3, 2, -1, 8]. The maximum subarray sum is 9, achieved by the subarray [2, -1, 8].
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def maximum_subarray_sum_with_single_element_doubling(nums: list[int]) -> int:
if not nums:
return 0
dp0, dp1 = nums[0], nums[0] * 2
max_val = max(dp0, dp1)
for i in range(1, len(nums)):
dp1 = max(nums[i] * 2, dp0 + nums[i] * 2, dp1 + nums[i])
dp0 = max(nums[i], dp0 + nums[i])
max_val = max(max_val, dp0, dp1)
return max_val