101 Logo
onenoughtone

Code Implementation

Maximum Subarray Finder Implementation

Below is the implementation of the maximum subarray finder:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * Find the maximum sum of a subarray with at most one element deletion.
 * Dynamic Programming approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The maximum sum of a subarray with at most one element deletion
 */
function maximumSum(arr) {
  const n = arr.length;
  
  // Handle edge case
  if (n === 1) {
    return arr[0];
  }
  
  // Initialize arrays
  const maxEndHere = new Array(n);
  const maxEndHereWithDeletion = new Array(n);
  
  maxEndHere[0] = arr[0];
  maxEndHereWithDeletion[0] = 0;
  let maxSoFar = arr[0];
  
  for (let i = 1; i < n; i++) {
    // Update maximum subarray sum ending at position i without deletion
    maxEndHere[i] = Math.max(arr[i], maxEndHere[i - 1] + arr[i]);
    
    // Update maximum subarray sum ending at position i with one deletion
    maxEndHereWithDeletion[i] = Math.max(
      maxEndHereWithDeletion[i - 1] + arr[i],
      maxEndHere[i - 1]
    );
    
    // Update maximum subarray sum so far
    maxSoFar = Math.max(maxSoFar, maxEndHere[i], maxEndHereWithDeletion[i]);
  }
  
  return maxSoFar;
}
 
/**
 * Find the maximum sum of a subarray with at most one element deletion.
 * Space-Optimized Dynamic Programming approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The maximum sum of a subarray with at most one element deletion
 */
function maximumSumOptimized(arr) {
  const n = arr.length;
  
  // Handle edge case
  if (n === 1) {
    return arr[0];
  }
  
  // Initialize variables
  let maxEndHere = arr[0];
  let maxEndHereWithDeletion = 0;
  let maxSoFar = arr[0];
  
  for (let i = 1; i < n; i++) {
    // Update maximum subarray sum ending at position i with one deletion
    maxEndHereWithDeletion = Math.max(
      maxEndHereWithDeletion + arr[i],
      maxEndHere
    );
    
    // Update maximum subarray sum ending at position i without deletion
    maxEndHere = Math.max(arr[i], maxEndHere + arr[i]);
    
    // Update maximum subarray sum so far
    maxSoFar = Math.max(maxSoFar, maxEndHere, maxEndHereWithDeletion);
  }
  
  return maxSoFar;
}
 
/**
 * Find the maximum sum of a subarray with at most one element deletion.
 * Prefix and Suffix Sum approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The maximum sum of a subarray with at most one element deletion
 */
function maximumSumPrefixSuffix(arr) {
  const n = arr.length;
  
  // Handle edge case
  if (n === 1) {
    return arr[0];
  }
  
  // Compute prefix sums (maximum subarray sum ending at each position)
  const prefix = new Array(n);
  prefix[0] = arr[0];
  
  for (let i = 1; i < n; i++) {
    prefix[i] = Math.max(arr[i], prefix[i - 1] + arr[i]);
  }
  
  // Compute suffix sums (maximum subarray sum starting from each position)
  const suffix = new Array(n);
  suffix[n - 1] = arr[n - 1];
  
  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = Math.max(arr[i], suffix[i + 1] + arr[i]);
  }
  
  // Find maximum subarray sum without deletion
  let maxWithoutDeletion = Math.max(...prefix);
  
  // Find maximum subarray sum with one deletion
  let maxWithDeletion = -Infinity;
  
  for (let i = 1; i < n - 1; i++) {
    maxWithDeletion = Math.max(maxWithDeletion, prefix[i - 1] + suffix[i + 1]);
  }
  
  // Return the maximum of the two
  return Math.max(maxWithoutDeletion, maxWithDeletion);
}
 
// Test cases
console.log(maximumSum([1, -2, 0, 3]));  // 4
console.log(maximumSum([1, -2, -2, 3]));  // 3
console.log(maximumSum([-1, -1, -1, -1]));  // -1
 
console.log(maximumSumOptimized([1, -2, 0, 3]));  // 4
console.log(maximumSumOptimized([1, -2, -2, 3]));  // 3
console.log(maximumSumOptimized([-1, -1, -1, -1]));  // -1
 
console.log(maximumSumPrefixSuffix([1, -2, 0, 3]));  // 4
console.log(maximumSumPrefixSuffix([1, -2, -2, 3]));  // 3
console.log(maximumSumPrefixSuffix([-1, -1, -1, -1]));  // -1

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: First, understand that we need to find the maximum sum of a subarray after removing at most one element from the array.
  2. Identify Key Insight: Recognize that this is an extension of the classic maximum subarray problem (Kadane's algorithm), but with the additional option of deleting one element.
  3. Define DP States: Define 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.
  4. Implement DP Solution: Implement the dynamic programming solution by updating the two states for each position in the array.
  5. Optimize Space: Optimize the space complexity by observing that we only need the values from the previous position to compute the current values.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone