CODEWITHSUNDEEP
c++algorithmrecursiondynamic-programmingmemoization
P.K.
P.K.

Reputation: 409

How do I memoize this recurrence relation?

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?

Upvotes: 0

Views: 237

Answers (1)

Emma
Emma

Reputation: 27723

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 analysis1, 2 in there.

Upvotes: 0

Related Questions