Maximum Countiguous Negative Sum or Mnimum positive subsequence sum problem

Question

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?

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

Answer 2

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.