101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. Space-Optimized Dynamic Programming - Complex approach
  3. Prefix and Suffix Sum Approach - Complex approach

Approach 1: Dynamic Programming Approach

The key insight for solving this problem is to use dynamic programming to keep track of two states: the maximum subarray sum ending at each position without any deletion, and the maximum subarray sum ending at each position with one deletion.

Let's define two arrays:

  • maxEndHere: Maximum subarray sum ending at position i without any deletion.
  • maxEndHereWithDeletion: Maximum subarray sum ending at position i with one deletion.

For each position i, we have two options:

  1. Include the current element in the subarray without any deletion.
  2. Delete the current element and connect the subarray ending at position i-1 with the subarray ending at position i-2.

Algorithm:

  1. Initialize maxEndHere[0] = arr[0] and maxEndHereWithDeletion[0] = 0.
  2. For each position i from 1 to n-1:
  3. a. Update maxEndHere[i] = max(arr[i], maxEndHere[i-1] + arr[i]).
  4. b. Update maxEndHereWithDeletion[i] = max(maxEndHereWithDeletion[i-1] + arr[i], maxEndHere[i-1]).
  5. Return the maximum value in both arrays.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array once, and each operation takes constant time.

Space Complexity:

O(n)

We use two arrays of size n to store the maximum subarray sums ending at each position.

Approach 2: Space-Optimized Dynamic Programming

We can optimize the space complexity of the dynamic programming approach by observing that to compute the values for position i, we only need the values for positions i-1 and i-2.

This allows us to reduce the space complexity to O(1) by using just a few variables instead of arrays.

Algorithm:

  1. Initialize maxEndHere = arr[0], maxEndHereWithDeletion = 0, and maxSoFar = arr[0].
  2. For each position i from 1 to n-1:
  3. a. Update maxEndHereWithDeletion = max(maxEndHereWithDeletion + arr[i], maxEndHere).
  4. b. Update maxEndHere = max(arr[i], maxEndHere + arr[i]).
  5. c. Update maxSoFar = max(maxSoFar, maxEndHere, maxEndHereWithDeletion).
  6. Return maxSoFar.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array once, and each operation takes constant time.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 3: Prefix and Suffix Sum Approach

Another approach is to use prefix and suffix sums to find the maximum subarray sum with one deletion. The idea is to compute the maximum subarray sum ending at each position (prefix sum) and the maximum subarray sum starting from each position (suffix sum).

Then, for each position i, we can compute the maximum subarray sum if we delete the element at position i by combining the prefix sum ending at position i-1 and the suffix sum starting at position i+1.

Algorithm:

  1. Compute the maximum subarray sum ending at each position (prefix sum) using Kadane's algorithm.
  2. Compute the maximum subarray sum starting from each position (suffix sum) using Kadane's algorithm in reverse.
  3. For each position i, compute the maximum subarray sum if we delete the element at position i by combining prefix[i-1] and suffix[i+1].
  4. Return the maximum of the above value and the maximum subarray sum without any deletion.

Time Complexity:

O(n)

Where n is the length of the array. We iterate through the array three times, and each operation takes constant time.

Space Complexity:

O(n)

We use two arrays of size n to store the prefix and suffix sums.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function maximumSum(arr):
    n = length of arr
 
    // Initialize arrays
    maxEndHere = array of size n
    maxEndHereWithDeletion = array of size n
 
    maxEndHere[0] = arr[0]
    maxEndHereWithDeletion[0] = 0
    maxSoFar = arr[0]
 
    for i from 1 to n-1:
        // Update maximum subarray sum ending at position i without deletion
        maxEndHere[i] = max(arr[i], maxEndHere[i-1] + arr[i])
 
        // Update maximum subarray sum ending at position i with one deletion
        maxEndHereWithDeletion[i] = max(maxEndHereWithDeletion[i-1] + arr[i], maxEndHere[i-1])
 
        // Update maximum subarray sum so far
        maxSoFar = max(maxSoFar, maxEndHere[i], maxEndHereWithDeletion[i])
 
    return maxSoFar
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone