Два самых больших смежных поддерева

В настоящее время я выполняю задачу, похожую на задачу максимального смежного поддерева. Однако вместо того, чтобы найти только один смежный суб-массив, я могу найти до двух неперекрывающихся смежных субарреев.

Например, для приведенного ниже тестового случая, ответ 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

В то время как мой код действительно работает для примера тестового случая, показанного выше, он завершается неудачей для некоторых других тестовых случаев (которые мне недоступны). Есть ли какие-либо случаи edge, которые не перехватываются моим кодом? Где я ошибаюсь? Спасибо за помощь.

Я пытался придумать несколько таких крайних случаев, но не могу.

1 ответ

  1. Проблема, по-видимому, заключается в следующем:

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

    Добавление best(numsLeft - 1, 1, arrLeft)без уменьшения arrLeft означает, что» лучшие » результаты от первых numsLeft - 1значений в nums[]происходит в конце nums[] (at index numsLeft - 1). Это может быть не так.

    Поэтому код, скорее всего, завершится ошибкой, если существует более 2 положительных диапазонов, разделенных отрицательными значениями.

    Кроме того, dpмассив должен быть инициализирован чем-то явно вне диапазона, например LLONG_MIN, а не -1, что может быть законной суммой.