Два крупнейших смежных подмассива

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

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

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

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

0

Решение

Кажется, проблема в следующих строках:

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

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

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

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

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]