c++ - 我如何记住这种递归关系？

Question

我正在解决Maximum Subarray Sum with One Deletion在 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.

我想出了一个递归解决方案，如下所示:
类解决方案{
上市:
int helper(vector & n, vector & 缓存, 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 allInclusiveSum+=n[i];
maxVal=max(maxVal, allInclusiveSum);
if(i!=startIndex) {
最低值=最小值(最低值，n[i])；
sumWithOneDel=allInclusiveSum-lowestVal;
maxVal=max(maxVal, sumWithOneDel);
}
}

maxVal=max(maxVal, helper(n, cache, startIndex+1));

返回缓存[startIndex]=maxVal；
}

int maximumSum(vector & arr) {
int i=0, first=arr[0];
for(i=1;i if(arr[i]!=first) 中断；
if(i==arr.size()) 先返回；

vector 缓存(arr.size()，-1)；
返回助手(arr，缓存，0)；
}
};

不幸的是，这个 TLE。因为我用 startIndex+1 递归调用，我真的不认为我遇到了重叠的子问题。
有没有办法让我记住我的解决方案？如果不是，为什么？

Answer 1

使用动态规划，我们只需定义一个 std::vector有 N 行和两列，然后运行我们的 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) 内存。

引用

更多详情，您可以查看Discussion Board .有很多公认的解决方案，有多种 languages和解释，高效的算法，以及渐近的time/space复杂性分析1 , 2在那里。