Provide an algorithm for the following task Given an array o

Provide an algorithm for the following task. Given an array of real numbers A[1..n] (with entries positive/zero/negative), output the maximum value that can be obtained by multiplying all the elements in a contiguous subarray A[i..j]. Assume that you can do arithmetic with two real numbers in O(1) time. Prove the correctness and analyze the running time of your algorithm. For full credit your algorithm should work in time O(n).

Solution

tmax=1;

tmin=1;

max=1;

for i = 1 to n

{

if(A[i]>0)

{

tmax = tmax*A[i];

tmin = min(tmin*A[i],1);

}

else if (A[i]==0)

{

tmax=0;

tmin=0;

}

else

{   

t = tmax;

tmax = max(tmin*A[i],1);

tmin = t *A[i];

}

if(tmax>max)

{

max=tmax;

}

}

print max