Skip to main content
Talentd

Maximum Alternating Subarray Sum With One Deletion - Solution & Explanation

Medium3 min read
Practice this problem

Problem Statement

You are given an integer array nums.

You may delete at most one element from nums, then choose a subarray of the resulting array.

Return the maximum possible alternating sum of the chosen subarray.

The alternating sum of an array is the sum of its elements at even indices minus the sum of its elements at odd indices. The chosen subarray is reindexed starting from 0 before calculating its alternating sum.

 

Example 1:

Input: nums = [5,-5,1]

Output: 11

Explanation:

Choose not to delete an element and select the entire array. Its alternating sum is 5 - (-5) + 1 = 11, which is the maximum possible.

Example 2:

Input: nums = [10,-5,-100]

Output: 110

Explanation:

Delete nums[1] = -5 to obtain [10,-100], then select the entire resulting array. Its alternating sum is 10 - (-100) = 110, which is the maximum possible.

Example 3:

Input: nums = [4,7]

Output: 7

Explanation:

Choose not to delete an element and select the subarray [7]. Its alternating sum is 7, which is the maximum possible.

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105

Approach Overview

Problem Overview: You pick a subarray and apply alternating signs (+, -, +, ...) to its elements. You may delete one element from the subarray before summing. Return the maximum possible value. Deleting an element shifts the signs of everything after it, so you can't just drop a value and keep the rest of the signs fixed.

Approach 1: Brute Force Over Every Subarray and Deletion (O(n^3) time, O(1) space)

Fix a start index l and an end index r, then try every index to delete, plus the option of deleting nothing. For each candidate, recompute the signed sum from scratch. This is correct because it checks every legal configuration. It is too slow for n up to 10^5, but it gives you a baseline and helps you confirm the sign-flip rule on small inputs.

Approach 2: Fix the Start, Extend with a Running Sum (O(n^2) time, O(1) space)

For each start index, walk right and keep two running values: the alternating sum with no deletion used, and the best sum where one element has already been removed. Each step updates both values in constant time. This removes the innermost loop over deletions. It is a good intermediate answer if you can't see the single-pass DP yet.

Approach 3: Single-Pass DP with Sign States (O(n) time, O(1) space)

Track the best value ending at index i in four states: whether the element at i carries a + or - sign, and whether a deletion has been spent. Each state at i depends only on states at i-1 and i-2, so one left-to-right pass fills them in. The key observation is that deleting element j means the next kept element inherits j's sign. That lets a deletion transition come from two positions back. Keep a running global maximum over all valid end states. Because each index does a constant amount of work, the total is O(n) with O(1) extra space.

Recommended for interviews: Interviewers expect you to start with the brute force, explain why deletions break a naive prefix-sum approach, and then move to the O(n) DP. The brute force shows you understand the problem. The single-pass DP with explicit sign states shows you can design the state machine yourself. Practice the state transitions on paper before you code. Interviewers often ask you to justify each transition.

Related practice: dynamic programming, arrays, and prefix sum.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force (every subarray and deletion)O(n^3)O(1)Small inputs, verifying results
Fix Start with Running SumsO(n^2)O(1)Moderate n, intermediate step to DP
Single-Pass DP with Sign StatesO(n)O(1)General case, large n, interview answer

Video Solutions (5)

Leetcode 4072 | Maximum Alternating Subarray Sum With One Deletion | Leetcode weekly contest 522

CodeWithMeGuys21:22841 views
Video 1 of 5

Frequently Asked Questions

Is Maximum Alternating Subarray Sum With One Deletion easy or hard?
It is a medium-difficulty problem with an acceptance rate of about 30%. The brute force is easy to write, but finding the O(n) state transitions for the deletion case is the hard part. If you can derive the sign-inheritance rule for deletions, the rest of the code follows directly.
How to solve Maximum Alternating Subarray Sum With One Deletion in O(n)?
Scan the array once and maintain DP values for the best alternating sum ending at each index. Keep one set of states for subarrays with no deletion yet and another for subarrays where one element has been removed. When you delete an element, the next kept element takes the deleted element's sign, so that transition comes from two positions back. Track a global maximum across all states.
Maximum Alternating Subarray Sum With One Deletion Python/Java solution?
Python and Java solutions both use the same O(n) DP with rolling variables instead of a full DP table. In Python, you update the state variables in a loop over the array and return the global maximum. In Java, the logic is identical, with long used for sums to avoid overflow on large inputs.
What is the best approach for Maximum Alternating Subarray Sum With One Deletion?
The best approach is a single-pass dynamic programming solution that tracks sign states at each index, with separate states for whether a deletion has been used. It runs in O(n) time and uses O(1) extra space. Each index only depends on the previous two indices, so you never need to revisit earlier elements.
Is Maximum Alternating Subarray Sum With One Deletion asked at Google/Amazon/Meta?
FleetCode tags this problem under General, so it is not mapped to a specific company in our data. Check company-tagged question lists on other platforms for recent interview reports. The DP pattern it uses appears often in interviews, so practicing it is useful regardless of company.
What data structure is used in Maximum Alternating Subarray Sum With One Deletion?
No special data structure is required. The solution uses the input array plus a few scalar variables that store DP states for each sign and deletion status. Constant extra memory is enough because each state only needs the values from the previous one or two indices.
What is the time complexity of Maximum Alternating Subarray Sum With One Deletion?
The optimal solution runs in O(n) time, where n is the length of the array, because it makes one left-to-right pass with constant work per element. A brute force that tries every subarray and every deletion runs in O(n^3). The O(n) DP uses O(1) extra space.

Ready to solve this problem?

Practice Maximum Alternating Subarray Sum With One Deletion with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Pulse Value After One Subarray Rotation