How to find minimum positive contiguous sub sequence in O(n) time?

Question

We have this algorithm for finding maximum positive sub sequence in given sequence in O(n) time. Can anybody suggest similar algorithm for finding minimum positive contiguous sub sequence.

For example If given sequence is 1,2,3,4,5 answer should be 1. [5,-4,3,5,4] ->1 is the minimum positive sum of elements [5,-4].

Answer 1

There cannot be such algorithm. The lower bound for this problem is O(n log n). I'll prove it by reducing the element distinctness problem to it (actually to the non-negative variant of it).

Let's suppose we have an O(n) algorithm for this problem (the minimum non-negative subarray).

We want to find out if an array (e.g. A=[1, 2, -3, 4, 2]) has only distinct elements. To solve this problem, I could construct an array with the difference between consecutive elements (e.g. A'=[1, -5, 7, -2]) and run the O(n) algorithm we have. The original array only has distinct elements if and only if the minimum non-negative subarray is greater than 0.

If we had an O(n) algorithm to your problem, we would have an O(n) algorithm to element distinctness problem, which we know is not possible on a Turing machine.

Answer 2

We can have a O(n log n) algorithm as follow:

Assuming that we have an array prefix, which index i stores the sum of array A from 0 to i, so the sum of sub-array (i, j) is prefix[j] - prefix[i - 1].

Thus, in order to find the minimum positive sub-array ending at index j, so, we need to find the maximum element prefix[x], which less than prefix[j] and x < j. We can find that element in O(log n) time if we use a binary search tree.

Pseudo code:

int[]prefix = new int[A.length];
prefix[0] = A[0];
for(int i = 1; i < A.length; i++)
    prefix[i] = A[i] + prefix[i - 1];
int result = MAX_VALUE;
BinarySearchTree tree;
for(int i = 0; i < A.length; i++){
    if(A[i] > 0)
       result = min(result, A[i];
    int v = tree.getMaximumElementLessThan(prefix[i]);
    result = min(result, prefix[i] - v);
    tree.add(prefix[i]);
}