Time complexity help Max Product Subarray

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

I have solved the maximum product subarray problem using divide and conquer. Can someone help me with the time complexity of my solution . Whether it is O(log(n)) or O(nlog(n)) . I am confused please help.

code

struct node{

int premin,premax, sufmin,sufmax, p,prod;

};

node help(const vector &a,int s,int e){

node ans;

if(s==e)

{

    ans.premin=ans.sufmin=ans.sufmax=ans.p=ans.prod=ans.premax=a[s];

    return ans;

}

int m=(s+e)/2;

node l=help(a,s,m);

node r=help(a,m+1,e);

ans.p=max(l.p,max(r.p,max(l.sufmax*r.premax,l.sufmin*r.premin)));

ans.premax=max(l.premax,max(l.prod*r.premax,l.prod*r.premin));

ans.sufmax=max(r.sufmax,max(r.prod*l.sufmax,r.prod*l.sufmin));

ans.premin=min(l.premin,min(l.prod*r.premax,l.prod*r.premin));

ans.sufmin=min(r.sufmin,min(r.prod*l.sufmax,r.prod*l.sufmin));

ans.prod=l.prod*r.prod;

return ans;

}

int Solution::maxProduct(const vector &a) {

return help(a,0,a.size()-1).p;

}

My approach is either the max product subarray lie in left half or right half or be passing through the middle. In the third case the answer can be formed from max of following:

left part's maximum suffix product * right part's maximum prefix product

left part's minimum suffix product * right part's minimum prefix product

as elements can be negative

Rev.	By	When	Δ	Comment
en3	aman_naughty	2019-07-07 22:25:41	5	Tiny change: 'llowing:\nleft par' -> 'llowing:\n\nleft par'
en2	aman_naughty	2019-07-07 21:33:48	21
en1	aman_naughty	2019-07-07 21:31:41	1484	Initial revision (published)

Rev.

Lang.

When

Comment

en3