Given an array[] of integers (+ive , -ive, 0) find the subarray which gives the largest product.

Data Structure Used: Array

Algorithm & Expliantion

Lets us take an array = { 2,-25,4,5,-3,-5}

We take 3 variables P , N , Val

P=1 , N=0 , Val=0

first value is 2 , A[0] which is +ve . So we multiply both P & N with A[0] .
P=2 , N=0

now V[1] = -25 -ve .

We multiply P with -V[1] & N with -V[1] .

P=50
N=0

As V[1] is -ve we swap P & N .
P=0 , N=50

if V[i] == 0
We initialise P=1 , N=0

if( P < 1 ) /* analogous to kadane's algo's if( sumSoFar < 0 ) */ { P=1; N=0; } at every step val = max( val , P ) We proceed in the same fashion till the end . What we are trying to do is to maintain max Positive product so far & max -ve product so far . Hence when we encounter a -ve value we multiply both with - V[i] & then swap as -ve * -ve = +ve -ve * +ve = -ve Working Code #include

int swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}

int main()
{
int a[]={6,-1,2,-33,4,15,-7,28,-9,-10};
int maxp=1,maxn=0;
int i=0;
for(i=0;i<10;i++) { if(a[i]>0)
{
maxp*=a[i];
maxn*=a[i];
}
else
{
maxp*=-a[i];
maxn*=-a[i];
swap(&maxp,&maxn);
}


}

printf("%d",maxp);
}

Time Complexity O(N)
Space Conmplexity O(1)
Run Here https://ideone.com/VaKgk