我如何记忆这个重复关系？

Question

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);
    }
};

不幸的是，这是TLES。由于我使用startindex+1递归调用，所以我并不真的认为我遇到了重叠的子问题。

有办法让我记住我的解决方案吗？如果没有，为什么？

Answer 1

对于动态编程，我们只需定义一个包含N行和两列的std::vector，然后一次运行arr，并使用std::max查找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;
    }
};

同样是O(N)时间和O(N)内存。

• 有关其他详细信息，请参阅讨论板。有大量被接受的解决方案，有各种语言和解释，有效的算法，以及渐近的时间/空间复杂度分析^1，2在其中。