Longest positive sum substring

Question

I was wondering how could I get the longest positive-sum subsequence in a sequence:

For example I have -6 3 -4 4 -5, so the longest positive subsequence is 3 -4 4. In fact the sum is positive (3), and we couldn't add -6 neither -5 or it would have become negative.

It could be easily solvable in O(N^2), I think could exist something much more faster, like in O(NlogN)

Do you have any idea?

EDIT: the order must be preserved, and you can skip any number from the substring

EDIT2: I'm sorry if I caused confusion using the term "sebsequence", as @beaker pointed out I meant substring

Answer 1

O(n) space and time solution, will start with the code (sorry, Java ;-) and try to explain it later:

  public static int[] longestSubarray(int[] inp) {
    // array containing prefix sums up to a certain index i
    int[] p = new int[inp.length];
    p[0] = inp[0];
    for (int i = 1; i < inp.length; i++) {
      p[i] = p[i - 1] + inp[i];
    }

    // array Q from the description below
    int[] q = new int[inp.length];
    q[inp.length - 1] = p[inp.length - 1];
    for (int i = inp.length - 2; i >= 0; i--) {
      q[i] = Math.max(q[i + 1], p[i]);
    }

    int a = 0;
    int b = 0;
    int maxLen = 0;
    int curr;
    int[] res = new int[] {-1,-1};
    while (b < inp.length) {
      curr = a > 0 ? q[b] - p[a-1] : q[b];
      if (curr >= 0) {
        if(b-a > maxLen) {
          maxLen = b-a;
          res = new int[] {a,b};
        }
        b++;
      } else {
        a++;
      }
    }
    return res;
  }

• we are operating on input array A of size n
• Let's define array P as the array containing the prefix sum until index i so P[i] = sum(0,i) where `i = 0,1,...,n-1'
• let's notice that if u < v and P[u] <= P[v] then u will never be our ending point
• because of the above we can define an array Q which has Q[n-1] = P[n-1] and Q[i] = max(P[i], Q[i+1])
• now let's consider M_{a,b} which shows us the maximum sum subarray starting at a and ending at b or beyond. We know that M_{0,b} = Q[b] and that M_{a,b} = Q[b] - P[a-1]
• with the above information we can now initialise our a, b = 0 and start moving them. If the current value of M is bigger or equal to 0 then we know we will find (or already found) a subarray with sum >= 0, we then just need to compare b-a with the previously found length. Otherwise there's no subarray that starts at a and adheres to our constraints so we need to increment a.

Answer 2

Let's make a naive implementation and then improve it.

We move from the left to the right calculating partial sums and for each position we find the most-left partial sum such as the current partial sum is greater than that.

input a
int partialSums[len(a)]
for i in range(len(a)):
    partialSums[i] = (i == 0 ? 0 : partialSums[i - 1]) + a[i]
    if partialSums[i] > 0:
        answer = max(answer, i + 1)
    else:
        for j in range(i):
            if partialSums[i] - partialSums[j] > 0:
                answer = max(answer, i - j)
                break

This is O(n²). Now the part of finding the left-most "good" sum could be actually maintained via BST, where each node would be represented as a pair (partial sum, index) with a comparison by partial sum. Also each node should support a special field min that would be the minimum of indices in this subtree.

Now instead of the straightforward search of an appropriate partial sum we could descend the BST using the current partial sum as a key following the next three rules (assuming C is the current node, L and R are the roots of the left and the right subtrees respectively):

1. Maintain the current minimal index of "good" partial sums found in curMin, initially +∞.
2. If C.partial_sum is "good" then update curMin with C.index.
3. If we go to R then update curMin with L.min.

And then update the answer with i - curMin, also add the current partial sum to the BST.

That would give us O(n * log n).