Все мы слышали о прекрасной задаче Бентли о жемчужинах программирования, которая решает максимальную сумму подпоследовательности:
maxsofar = 0;
maxcur = 0;
for (i = 0; i < n; i++) {
maxcur = max(A[i] + maxcur, 0);
maxsofar = max(maxsofar, maxcur);
}
Что, если мы добавим дополнительное условие максимальной подпоследовательности, которая меньше M?
Это должно сделать это. Я прав?
int maxsofar = 0;
for (int i = 0; i < n - 1; i++) {
int maxcur = 0;
for (int j = i; j < n; j++) {
maxcur = max(A[j] + maxcur, 0);
maxsofar = maxcur < M ? max(maxsofar, maxcur) : maxsofar;
}
}
К сожалению, это O(n^2). Вы можете немного ускорить его, разорвав внутренний цикл, когда maxcur >=M, но все еще остается n^2.
Это можно решить с помощью динамического программирования, но только за псевдополиномиальное время.
Определять
m(i,s) := maximum sum less than s obtainable using only the first i elements
Затем вы можете рассчитать max(n,M), используя следующее рекуррентное соотношение
m(i,s) = max(m(i-1,s), m(i-1,s-A[i]]+A[i]))
Это решение аналогично решению задачи о рюкзаке.
Если все A[i] > 0, вы можете сделать это в O(n lg n): предварительно вычислить частичные суммы S[i], затем двоичный поиск S для S[i] + M. Например:
def binary_search(L, x):
def _binary_search(lo, hi):
if lo >= hi: return lo
mid = lo + (hi-lo)/2
if x < L[mid]:
return _binary_search(lo, mid)
return _binary_search(mid+1, hi)
return _binary_search(0, len(L))
A = [1, 2, 3, 2, 1]
M = 4
S = [A[0]]
for a in A[1:]:
S.append(S[-1] + a)
maxsum = 0
for i, s in enumerate(S):
j = binary_search(S, s + M)
if j == len(S):
break
sum = S[j-1] - S[i]
maxsum = max(sum, maxsum)
print maxsum
РЕДАКТИРОВАТЬ: как правильно указывает atuls, бинарный поиск является излишним; поскольку S увеличивается, мы можем просто отслеживать j на каждой итерации и двигаться дальше.
A[i]; бинарный поиск не работает.
- person fearlesstost; 12.07.2011
Разрешимо за O (n log (n)). Использование двоичного дерева поиска (сбалансированного) для поиска наименьшего значения, превышающего сумму-M, а затем обновления минимума и вставки суммы слева направо. Где sum - это частичная сумма на данный момент.
best = -infinity;
sum = 0;
tree.insert(0);
for(i = 0; i < n; i++) {
sum = sum + A[i];
int diff = sum - tree.find_smallest_value_larger_than(sum - M);
if (diff > best) {
best = diff;
}
tree.insert(sum);
}
print best
