# Count positive subsequences in a sequence of numbers faster than $\Theta(n^{1.5})$

Find the total number of positive subsequences in a sequence of numbers with an algorithm that is faster than $O(n^{1.5})$. For example, {-2 3} is a positive subsequence of {1 -2 3} since -2+3 = 1 is positive. The following is my code:

import java.util.*;

class PSIv3
{

public static int mergeSort(int[] a, int i, int j){
int count = 0;

if ( i < j ){
int mid = (i+j)/2;
count += mergeSort(a, i, mid);
count += mergeSort(a, mid+1, j);
count += merge(a, i, mid, j);
} else {

if ( a[i] > 0 ){
count++;
return count;
}

}

return count;
}

public static int merge(int[] a, int i, int mid, int j){

int sum = a[mid] + a[mid+1];
int count = 0;
int tempsum;

if (sum > 0)
count++;

for ( int l = mid + 2; l <= j; l++ ){
sum = sum + a[l];
if ( sum > 0 ){
count++;
}
}

sum = a[mid] + a[mid+1];

for ( int k = mid - 1; k >= i; k-- ){
sum = sum + a[k];

if ( sum > 0 )
count++;

tempsum = sum;

for ( int l = mid + 2; l <= j; l++ ){
tempsum = tempsum + a[l];
if ( tempsum > 0 ){
count++;
}
}

}

return count;
}

public static void main(String [] args)
{
Scanner sc = new Scanner(System.in);
int numberOfElements = sc.nextInt();
int[] intArray = new int[numberOfElements];

for ( int i = 0; i < numberOfElements; i++ ){
intArray[i] = sc.nextInt();
}

int count = PSIv3.mergeSort(intArray, 0, numberOfElements-1);

System.out.println(count);

}
}


My algorithm is to modify the mergeSort algorithm with the aim of getting an $O(N log N)$ algorithm. Instead of sorting, I increment the count when I encounter a positive subsequence. When two portions, say A and B merge together, there are 3 possibilities to consider: 1) the subsequence is in A 2) the subsequence is in B or 3)the subsequence is not in A and not in B. Since 1) and 2) are already counted. I only have to consider 3. Every subsequence in 3 must contain a[mid] and a[mid+1]. Else it will be in 1) or 2). Therefore, I start from this subsequence and expand to the left and expand to the right, incrementing the count if the subsequence is positive.

My algorithm works, but it is not fast enough to pass the test. Hence, I am wondering if anyone has a faster algorithm or can tell me how to optimise the existing algorithm. Thanks.

• Is it important for the Java code to be fast? If so, this doesn't belong here. Otherwise, please replace the code with pseudocode. – Yuval Filmus Oct 25 '14 at 15:53
• what do you mean? @YuvalFilmus – user10024395 Oct 25 '14 at 17:33
• Sorry I wasn't clear. If this is a question about Java, say you're Wondering why your Java implementation is too slow, then it doesn't belong here. Otherwise, there is no reason for us to see Java code. – Yuval Filmus Oct 25 '14 at 18:57
• i am asking about algorithm – user10024395 Oct 25 '14 at 19:22
• If the code can be ignored, either remove it or replace it with pseudocode. Also, if your code really runs in $O(N\log N)$, how come it is not "fast enough to pass the test"? Which test? – Yuval Filmus Oct 25 '14 at 21:44

## 1 Answer

The running time for merge procedure is $O(n^2)$ instead of $O(n)$, so your running time $T(n) = 2T(n/2) + O(n^2) = O(n^2)$. The $O(n^2)$ time is caused by your second half of the 'merge' procedure, where you compute the sum including the right subarray for each left subarray. If you could find a way to make your 'merge' linear time, then the algorithm will be $O(n \lg{n})$.