How do I memoize this recurrence relation?

Question

I am solving Maximum Subarray Sum with One Deletion on LeetCode:

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. For input arr = [1,-2,0,3], output should be 4.

I came up with a recursive solution as below:

class Solution {
public:
    int helper(vector<int>& n, vector<int>& cache, int startIndex) {
        if(startIndex>=n.size()) return INT_MIN;
        if(cache[startIndex]!=-1) return cache[startIndex];
        
        int allInclusiveSum=0, sumWithOneDel=0, lowestVal=INT_MAX, maxVal=INT_MIN;
        for(int i=startIndex; i<n.size(); i++) {
            allInclusiveSum+=n[i];
            maxVal=max(maxVal, allInclusiveSum);
            if(i!=startIndex) {
                lowestVal=min(lowestVal, n[i]);
                sumWithOneDel=allInclusiveSum-lowestVal;
                maxVal=max(maxVal, sumWithOneDel);
            }
        }
        
        maxVal=max(maxVal, helper(n, cache, startIndex+1));
        
        return cache[startIndex]=maxVal;
    }
    
    int maximumSum(vector<int>& arr) {
        int i=0, first=arr[0];
        for(i=1; i<arr.size(); i++)
            if(arr[i]!=first) break;
        if(i==arr.size()) return first;
        
        vector<int> cache(arr.size(), -1);
        return helper(arr, cache, 0);
    }
};

Unfortunately, this TLEs. Since I call recursively with startIndex+1, I don't really think I am encountering overlapping sub-problems.

Is there a way I could memoize my solution? If no, why?

Hmm, 26 views and no comment makes me feel I have missed something/my question is incorrect. Could someone please point out, so that I could edit it? Thanks! — P.K.
Here is view 27 ;-). Thing is, understanding your (or any) algorithm would take too long for me now, let alone understanding the subtle differences to another one ;-). — Peter - Reinstate Monica
There's an awful lot of code here and no real guidance on where to start looking for the problem. When I hear "memoize" I immediately think "Why not use a std::map to cache?" and yet I don't see one, so... — tadman
@user3386109, so I guess my mistake was that I was using a combination of recursion and iteration, which is why I could not effective cache it. (It was just brute-force in essence). Thank you, that helps! :) — P.K.
I'm inclined to just let this one go. You can always self-answer :) — user3386109

Emma Emma · Accepted Answer · 2020-07-07T15:53:57

With dynamic programming, we would just define a std::vector with N rows and two columns, then run through our arr in one pass, and use std::max to find max_sum:

#include <vector>
#include <algorithm>


class Solution {
public:
    static inline int maximumSum(const std::vector<int> &arr) {
        int length = arr.size();
        std::vector<std::vector<int>> dynamic_sums(length, std::vector<int>(2, 0));
        dynamic_sums[0][0] = arr[0];
        int max_sum = arr[0];

        for (unsigned int row = 1; row < length; row++) {
            dynamic_sums[row][0] = std::max(arr[row], dynamic_sums[row - 1][0] + arr[row]);
            dynamic_sums[row][1] = std::max(arr[row], std::max(dynamic_sums[row - 1][1] + arr[row], dynamic_sums[row - 1][0]));
            max_sum = std::max(max_sum, std::max(dynamic_sums[row][0], dynamic_sums[row][1]));
        }

        return max_sum;
    }
};

It's similarly O(N) time and O(N) memory.

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

How do I memoize this recurrence relation?

1 Answers

References