Задача о суммировании максимальной отрицательной суммы или минимальной положительной подпоследовательности - PullRequest
Новая
       41

Задача о суммировании максимальной отрицательной суммы или минимальной положительной подпоследовательности

3 голосов
/ 12 июля 2011

Мы все слышали о красивой задаче Бентли о жемчужинах, которая решает максимальную сумму подпоследовательности: 

maxsofar = 0;
maxcur = 0;
for (i = 0; i < n; i++) {
  maxcur = max(A[i] + maxcur, 0);
  maxsofar = max(maxsofar, maxcur);
}

Что если мы добавим дополнительное условие максимальной подпоследовательности, которое меньше М?

Ответы [ 4 ]

1 голос
/ 12 июля 2011

Если все 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 каждую итерацию и продвигаться оттуда.

1 голос
/ 12 июля 2011

Это может быть решено с помощью динамического программирования, хотя только в псевдополиномиальное время.

Определение 

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]))

Это решение аналогично решению задачи о ранце.

1 голос
/ 12 июля 2011

Это должно сделать это. Я прав? 

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 остается.

0 голосов
/ 13 июля 2011

разрешимо в O (n log (n)). Использование бинарного дерева поиска (сбалансированного) для поиска наименьшего значения, большего, чем sum-M, а затем обновления min и вставки суммы, переходя слева направо. Где сумма является частичной суммой до сих пор. 

  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
...