Tejav
#3410

Maximize Subarray Sum After Removing All Occurrences of One Element

Hard
ArrayDynamic ProgrammingSegment TreeKadane's AlgorithmHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages a single pass to calculate the maximum subarray sum while also keeping track of the sums when removing each unique element. This avoids the need for multiple passes through the array.

⚙️

Algorithm

4 steps
  1. 1Step 1: Create a frequency map to count occurrences of each element.
  2. 2Step 2: Use Kadane's algorithm to calculate the maximum subarray sum for the original array.
  3. 3Step 3: For each unique element, calculate the maximum subarray sum excluding that element using a modified Kadane's algorithm.
  4. 4Step 4: Return the maximum of the original maximum subarray sum and the maximum sums found after removing each unique element.
solution.py23 lines
1# Full working Python code
2import numpy as np
3from collections import defaultdict
4
5class Solution:
6    def maxSumAfterRemovingElement(self, nums):
7        freq = defaultdict(int)
8        for num in nums:
9            freq[num] += 1
10        
11        max_sum = self.kadane(nums)
12        
13        for x in freq.keys():
14            filtered_sum = self.kadane([num for num in nums if num != x])
15            max_sum = max(max_sum, filtered_sum)
16        return max_sum
17    
18    def kadane(self, arr):
19        max_ending_here = max_so_far = arr[0] if arr else 0
20        for x in arr[1:]:
21            max_ending_here = max(x, max_ending_here + x)
22            max_so_far = max(max_so_far, max_ending_here)
23        return max_so_far
ℹ

Complexity note: The time complexity is O(n) because we traverse the array a constant number of times (once for counting and once for Kadane's). The space complexity is O(n) due to the frequency map.

  • 1Removing an element can potentially increase the maximum subarray sum if that element is negative.
  • 2Kadane's algorithm is a powerful tool for finding maximum subarray sums efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.