The longest substring with a positive sum

Question

I was wondering how I can get the longest subsequence with a positive sum in the sequence:

For example, I have -6 3 -4 4 -5, so the longest positive subsequence is 3 -4 4. Actually, the sum is positive (3), and we could not add -6 nor -5 or it would become negative.

It can be easily solvable in O (N ^ 2), I think that something much faster can exist, for example, in O (NlogN)

Do you have any ideas?

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

EDIT2: Sorry if I caused confusion using the term "sebsequence", as @beaker indicated that I meant the substring

Answer 1

O(n) A space-time solution, 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(ba > maxLen) { maxLen = ba; res = new int[] {a,b}; } b++; } else { a++; } } return res; } 

• we work with an input array A size n
• Define an array P as an array containing the sum of the prefix to index i , therefore P[i] = sum(0,i) where 'i = 0,1, ..., n-1'
• Note that if u < v and P[u] <= P[v] , then u will never be our endpoint
• Because of the above, we can define an array Q that has Q[n-1] = P[n-1] and Q[i] = max(P[i], Q[i+1])
• Now let's look at M_{a,b} , which shows us a subarray of the maximum amount, starting with a and ending with b or higher. We know that M_{0,b} = Q[b] and that M_{a,b} = Q[b] - P[a-1]
• using the above information, we can now initialize our a, b = 0 and start moving them. If the current value of M greater than or equal to 0, then we know that we will find (or have already found) a sublattice with the sum> = 0, then we just need to compare ba with the previously found length. Otherwise, there is no subarray that starts at a and adheres to our restrictions, so we need to increase a .

Answer 2

Make a naive implementation and then improve it.

We move from left to right, calculating the partial sums, and for each position we find the leftmost partial sum, such as the current partial sum, more.

 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 “best” sum can actually be saved through BST , where each node will be represented as a pair (partial sum, index) with a partial sum comparison. Also, each node must support a special min field, which would be the minimum indices in this subtree.

Now, instead of simply looking for a suitable partial sum, we could go down BST using the current partial sum as the key following the following three rules (assuming C is the current node, L and R are the roots of the left and right subtrees, respectively):

• Maintaining the current minimum index of “good” partial sums found in curMin is initially +∞ .
• If C.partial_sum is “good,” update curMin with C.index .
• If we move to R , update curMin with L.min .

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

This will give us O (n * log n).

Answer 3

We can easily have an O (n log n) solution for the longest subsequence .

• First sort the array, remember their indices.

• Select all the largest numbers, stop when their sum is negative, and you will get a response.

• Restore your original order.

Pseudo code

  sort(data); int length = 0; long sum = 0; boolean[] result = new boolean[n]; for(int i = n ; i >= 1; i--){ if(sum + data[i] <= 0) break; sum += data[i]; result[data[i].index] = true; length++; } for(int i = 1; i <= n; i++) if(result[i]) print i; 

So, instead of waiting, I propose a solution O (n log n) for the longest positive substring .

• First we create a prefix array, which is the sum of the array prefix.

• Secondly, we use binary search to find the longest length with a positive sum

Pseudo code

  int[]prefix = new int[n]; for(int i = 1; i <= n; i++) prefix[i] = data[i]; if(i - 1 >= 1) prefix[i] += prefix[i - 1]; int min = 0; int max = n; int result = 0; while(min <= max){ int mid = (min + max)/2; boolean ok = false; for(int i = 1; i <= n; i++){ if(i > mid && pre[i] - pre[i - mid] > 0){//How we can find sum of segment with mid length, and end at index i ok = true; break; } } if(ok){ result = max(result, mid) min = mid + 1; }else{ max = mid - 1; } } 

So, the above algorithm is incorrect, as piotrekg2 pointed out, what we need to do is

• create a prefix array, which is the prefix of the sum of the array.

• Detach the prefix array and we need to remember the index of the prefix array.

• Iterating through a prefix array that preserves the minimum index that we have encountered so far, the maximum difference between the index is the answer.

Note: when we compare the value in prefix , if two indexes have equivalent values , therefore with a lower index more , this will avoid the case when the sum is 0.

Pseudocode:

  class Node{ int val, index; } Node[]prefix = new Node[n]; for(int i = 1; i <= n; i++) prefix[i] = new Node(data[i],i); if(i - 1 >= 1) prefix[i].val += prefix[i - 1].val; sort(prefix); int min = prefix[1].index; int result = 0; for(int i = 2; i <= n; i ++) if(prefix[i].index > min) result = max(prefix[i].index - min + 1, result) min = min(min, prefix[i].index);