0

我目前正在做一个类似于最大连续子阵列问题的问题。但是，我可以找到最多两个不重叠的连续子阵列，而不是只找到一个连续的子阵列。

例如，对于下面的测试用例，答案是 20，因为我们可以取除 -20 之外的所有值。

5 3 -20 4 8

为此，我实现了以下代码：

long long n, nums[500500], dp[500500][2][3];

long long best(int numsLeft, int beenTaking, int arrLeft) {
    if (arrLeft < 0 || numsLeft < 0) return 0;

    if (dp[numsLeft][beenTaking][arrLeft] != -1)
        return dp[numsLeft][beenTaking][arrLeft];

    if (beenTaking) {
        // continue Taking
        long long c1 = best(numsLeft - 1, beenTaking, arrLeft) + nums[numsLeft];
        // stop Taking
        long long c2 = best(numsLeft - 1, 0, arrLeft);

        return dp[numsLeft][beenTaking][arrLeft] = max(c1, c2);
    } else {
        // continue not Taking
        long long c1 = best(numsLeft - 1, beenTaking, arrLeft);
        // start Taking
        long long c2 = best(numsLeft - 1, 1, arrLeft - 1) + nums[numsLeft];

        return dp[numsLeft][beenTaking][arrLeft] = max(c1,c2);
    }
}

这是函数调用：

cout << best(n - 1, 0, 2) << endl;

dp 数组在函数调用之前已经填充了 -1。nums 数组包含 n 个元素并且是零索引的。

Ideone.com 链接是这样的：http: //ideone.com/P5PB7h

虽然我的代码确实适用于上面显示的示例测试用例，但它对于其他一些测试用例（我不可用）却失败了。是否有任何边缘情况没有被我的代码捕获？我哪里错了？感谢您的帮助。

我尝试提出一些这样的边缘案例，但我无法这样做。

4

1 回答 1

0

问题似乎在以下几行：

if (beenTaking) {
    // continue Taking
    long long c1 = best(numsLeft - 1, beenTaking, arrLeft) + nums[numsLeft];
    ...
} else {
    ...
}

在不递减 arrLeft 的情况下添加best(numsLeft - 1, 1, arrLeft)意味着“最佳”结果来自 in 的第一个numsLeft - 1值，nums[]发生在 nums[] 的末尾（在 index 处numsLeft - 1）。这可能不是真的。

因此，当有超过 2 个由负值分隔的正范围时，代码可能会失败。

此外，dp应该将数组初始化为明显超出范围的值，例如 LLONG_MIN，而不是 -1，这可能是一个合法的总和。

于 2017-01-01T06:46:25.463 回答