Leetcode Problem 1186. Maximum Subarray Sum with One Deletion

1186. Maximum Subarray Sum with One Deletion

Leetcode Solutions

Dynamic Programming with Optional Deletion

  1. Initialize maxEndHere and maxStartHere arrays with the size of the input array arr.
  2. Set maxEndHere[0] to arr[0] and iterate through the array to fill in the rest of maxEndHere using the formula maxEndHere[i] = Math.max(arr[i], maxEndHere[i-1] + arr[i]).
  3. Set maxStartHere[arr.length - 1] to arr[arr.length - 1] and iterate backwards through the array to fill in the rest of maxStartHere using the formula maxStartHere[i] = Math.max(arr[i], maxStartHere[i+1] + arr[i]).
  4. Initialize max to the maximum value in maxEndHere array.
  5. Iterate through the array from the second element to the second to last element, and for each index i, calculate the sum if the element at index i is deleted: maxEndHere[i-1] + maxStartHere[i+1].
  6. Update max if the calculated sum is greater than the current max.
  7. Return max as the result.
UML Thumbnail

Single Pass Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...