Time complexity help Max Product Subarray

Revision en2, by aman_naughty, 2019-07-07 21:33:48

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

My approach is either the max product subarray lie in left half or right half or be passing throug 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

Tags #interview, #dp, divide and conquer, #help

History

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