MCSP

How do you get an O(n) running time of a Maximum Consecutive Sub-sequence Product. I have a O(n^2) algorithm now, but I need a O(n) runtime.

ar is the array

k=ar.length;
          

            pro=BigInteger.ONE;
            max=BigInteger.valueOf(ar[0]);
            for(i=0;i<k;i++)
            {
                pro=BigInteger.valueOf(ar[i]);
                if(pro.compareTo(max)>0) {
                    max=pro;
                }
                for(j=i+1;j<k;j++)
                {
                    pro=pro.multiply(BigInteger.valueOf(ar[j]));
                    if(pro.compareTo(max)>0) 
                        max=pro;
                }

This may work:

-Split array into sub-arrays between zeros. (O(n))
-Check how many negative numbers each sub-array has. (O(n))
-If even, then multiply out the whole sub-array. (O(n))
-If odd, then you would have two products: one using everything after the first negative number and one using everything before the last negative number. Take the larger of the two. (O(n))
-Find the largest value out of all the sub-arrays. (O(n))