3

We all heard of bentley's beautiful proramming pearls problem which solves maximum subsequence sum:

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

What if we add an additional condition maximum subsequence that is lesser M?

Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
atuls
  • 61
  • 6

4 Answers4

1

This should do this. Am I wright?

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;
   }
}

Unfortunately this is O(n^2). You may speed it up a little bit by breaking the inner loop when maxcur >=M, but still n^2 remains.

Przemek Kryger
  • 687
  • 4
  • 11
1

If all A[i] > 0, you can do this in O(n lg n): precompute partial sums S[i], then binary search S for S[i] + M. For instance:

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

EDIT: as atuls correctly points out, the binary search is overkill; since S is increasing, we can just keep track of j each iteration and advance from there.

fearlesstost
  • 866
  • 6
  • 7
  • it an be negative too. And what is S[i]+M? – atuls Jul 12 '11 at 16:48
  • edited to make that clearer - but no, this doesn't take into account the possibility of negative `A[i]`; the binary search won't work. – fearlesstost Jul 12 '11 at 19:16
  • You don't need binary search, linear search is good. Entire loop will finish in O(n), because the next search is to the right of previous. But still doesn't work for negative numbers. – atuls Jul 13 '11 at 04:42
1

This can be solved using dynamic programming albeit only in pseudo-polynomial time.

Define

m(i,s) := maximum sum less than s obtainable using only the first i elements

Then you can calculate max(n,M) using the following recurrence relation

m(i,s) = max(m(i-1,s), m(i-1,s-A[i]]+A[i]))

This solution is similar to the solution to the knapsack problem.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
0

Solveable in O(n log(n)). Using a binary search tree (balanced) to search for smallest value larger than sum-M, and then update min, and insert sum, by going from left to right. Where sum is the partial sum so far.

  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
atuls
  • 61
  • 6