From Brute Force to Space Optimal DP (C++)
Note\nThis article assumes basic understanding of recursion and dynamic programming but does not require specific knowledge about cumulative sum or the Kadane a
## Note\nThis article assumes basic understanding of recursion and dynamic programming but does not require specific knowledge about cumulative sum or the Kadane algorithm.\n\n## Approach 1: Brute Force (Time Limit Exceeded)\n\nWithout further consideration, the easiest way is just simulating the question. We could take each subarray and remove each element from the subarray once. We then calculate the maximum sum of remaining elements. Note that the subarray must not be empty after deleting an element, therefore we only generate subarrays spanning over 2 or more elements. The case of not deleting an element from the subarray is covered by deleting an element from the subarray of 1 more element, with the only exception being the whole array as a solution when all values are positive.\n\n```cpp\nint maximumSum(vector<int>& arr) {\n\tint result = INT_MIN;\n\tfor (int i = 0; i < arr.size(); i++)\n\t\tfor (int j = i+1; j < arr.size(); j++)\n\t\t\tfor (int k = i; k <= j; k++) {\n\t\t\t\tint sum = 0;\n\t\t\t\tfor (int l = i; l < k; l++) \n\t\t\t\t\tsum += arr[l];\n\t\t\t\tfor (int l = k+1; l <= j; l++) \n\t\t\t\t\tsum += arr[l];\n\t\t\t\tresult = max(result, sum);\n\t\t\t}\n\t//In case the entire array is a better solution\n\tint total = 0;\n\tfor (int i = 0; i < arr.size(); i++)\n\t\ttotal += arr[i];\n\treturn max(result, total);\n}\n```\nTime complexity: O(N^4). Space complexity: O(1).\n\nThe solution above can be improved by storing the cumulative sum. For the uninitiated, it is a common technique to avoid calculating the sum over and over again. It is explained in detail here https://leetcode.com/articles/subarray-sum-equals-k .\n```cpp\nint maximumSum(vector<int>& arr) {\n\tvector<int> prefix (arr.size()+1, 0);\n\tfor (int i = 0; i < arr.size(); i++)\n\t\tprefix[i+1] = prefix[i] + arr[i];\n\n\tint result = INT_MIN;\n\tfor (int i = 0; i < arr.size(); i++)\n\t\tfor (int j = i+1; j < arr.size(); j++) {\n            int sum = prefix[j+1] - prefix[i];\n            for (int k = i; k <= j; k++)\n\t\t\t\tresult = max(result, sum - arr[k]);\n\t\t}\n    int total = 0;\n    for (int i = 0; i < arr.size(); i++)\n        total += arr[i];\n\treturn max(result, total);\n}\n```\nTime complexity: O(N^3). Space complexity: O(N).\n\n\n## Approach 2: Top-Down Dynamic Programming with Memoization (Stack Overflow)\n\nThe brute-force solution is wasteful, because it computes the connection between the exact ranges of subarrays and their values, the sum with at most 1 deletion in this case. It then drops the information of the ranges because the question only asks for the sum. \n\nSimilarly to the simpler variation of the problem, https://leetcode.com/problems/maximum-subarray/, we could fix an end of the subarray, for instance the starting index, and find the best choice of the ending index in order to maximize the sum. Using recursion, we could keep choosing the larger one between just the element `cur` to end the subarray here, and `cur + recursion(next ...)` to extend the subarray. In the end, we combine all the partial solutions to find out the global maximum.\n\nThe difference to the original problem is the element removal, which can be seen as part of the recursion\'s state: If no element has been removed so far, we can remove one in the next round, otherwise we are not allowed to remove anymore. Now that `maximumSumFrom(i)` recursively depends on the result of `maximumSumFrom(i+1), maximumSumFrom(i+2), ..., maximumSumFrom(n-1)`, it overlaps with other subproblems. To avoid repeated calculations, we could use memoization to cache the results.\n\n```cpp\nint maximumSum(vector<int>& arr) {\n\tint result = INT_MIN;\n\tunordered_map<int, unordered_map<bool, int>> memo;\n\n\t// The max sum with at most 1 deletion is the max of partial max sum starting at each index (and ending anywhere) with at most 1 deletion\n\tfor (int i = 0; i < arr.size(); i++)\n\t\tresult = max(result, maximumSumFrom(memo, arr, i, true));\n\treturn result;\n}\n\n// Returns the maximum sum among all possible non-empty subarrays starting at index (inclusive) with deletion either allowed or disallowed\n// start: the index where the subarray starts (inclusive)\n// canDelete: when true, the subarray may optionally exclude an element, otherwise it must include all elements starting from \'start\'\nint maximumSumFrom(unordered_map<int, unordered_map<bool, int>>& memo, vector<int>& arr, int start, bool canDelete) {\n\tif (memo.find(start) != memo.end() && memo[start].find(canDelete) != memo[start].end())\n\t\treturn memo[start][canDelete];\n\n\tint res;\n\n\t// Base case when only 1 element is left: To make the subaray non-empty, we have to include the element regardless of canDelete\n\tif (start == arr.size() - 1) {\n\t\tres = arr[start];\n\t} else {\n\t\tif (canDelete) {\n\t\t\t// The case to include the current element and allow deletion afterwards\n\t\t\t// The subarray may end anywhere, therefore we take the best result out of the current element and current + recursion\n\t\t\tint pick = max(arr[start], arr[start] + maximumSumFrom(memo, arr, start + 1, true));\n\n\t\t\t// The case to drop the current element and forbid deletion afterwards\n\t\t\tint drop = maximumSumFrom(memo, arr, start + 1, false);\n\t\t\tres = max(pick, drop);\n\t\t} else { \n\t\t\t// Deletion is forbidden, we must pick the element and forbid deletion further\n\t\t\tres = max(arr[start], arr[start] + maximumSumFrom(memo, arr, start + 1, false));\n\t\t}\n\t}\n\n\tmemo[start][canDelete] = res;\n\treturn res;\n}\n```\nTime complexity: O(N) because every possible partial solution (index x canDelete) is calculated exactly once before being cached.\nSpace complexity: O(N), all partial solutions are cached\n\n\n## Approach 3: Bottom-Up Dynamic Programming (Accepted, Optimal)\n\nThe top-down DP solution causes stack overflow on large data sets, because every recursion depth adds a level to the call stack and would exhaust the stack memory at some point.\nIn the top-down solution, it is noticeable that the dependency between recursions has a fixed direction: `maximumSumFrom(..., i)` always depends on a larger index `maximumSumFrom(..., i+1)`, which means instead of lazily computing the partial solutions, we could fill the partial solutions in a particular order that satisfies the data dependency. \n\nFor convenience, let\'s invert the direction of the recursion.\nLet `keep[i]` be the maximum sum of non-empty subarray ending _at_ ith position (inclusive), and `del[i]` be the max sum of non-empty subarray that also ends at the ith position (inclusive) but _allows_ deleting an element. This means the end of these subarrays are known, but we don\'t particularly care about where they start. The invariant constraint is that the subarray is non-empty after deleting at most 1 element.\nThe base cases for `keep[0]` and `del[0]` are both just the first element `arr[0]` because an empty subarray is forbidden. In this case, allowing deleting an element doesn\'t make a difference.\n\n```cpp\nint maximumSum(vector<int>& arr) {\n\tint n = arr.size(), res = arr[0];\n\tvector<int> keep (n), del (n);\n\n\t// Initialize the base cases \n\tkeep[0] = del[0] = arr[0];\n\n\tfor (int i = 1; i < n; i++) {\n\n\t\t// The max sum of full subarray without deleting any element is the larger one between the current element\n\t\t// and (current + previous full subarray). This part is the same as the Kadane algorithm. \n\t\tkeep[i] = max(keep[i - 1], 0) + arr[i]; \n\n\t\t// The max sum of "deleted" subarray can be evolved from the previous full subarray by dropping the current element,\n\t\t// or by having dropped some element previously and include the current element.\n\t\tdel[i] = max(keep[i - 1], del[i - 1] + arr[i]);\n\n\t\t// Keep track of the global maximum\n\t\tres = max({ res, keep[i], del[i] });\n\t}\n\treturn res;\n}\n```\nTime complexity: O(N) \nSpace complexity: O(2*N) = O(N) for holding the same number of elements as the original array\n\nNow apparently each element in the DP solution only depends on the value of its previous index, which means we could reduce their dimensions by keeping only the previous and current states.\n\n```cpp\nint maximumSum(vector<int>& arr) {\n\tint n = arr.size(), res = arr[0], keep = arr[0], del = arr[0];\n\tfor (int i = 1; i < n; i++) {\n\t\tdel = max(keep, del + arr[i]);\n\t\tkeep = max(keep, 0) + arr[i];\n\t\tres = max({ res, keep, del });\n\t}\n\treturn res;\n}\n```\nTime complexity: O(N)\nSpace complexity: O(1)
[]