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;
                }

>>17
there can be up to 10,000 elements in the array, so I should probably use bigInteger

>>18
-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))

that makes more sense than doing all the calculations and then dividing out. But I would have to have a location of the last negative before I start doing the product?