Time complexity help

Правка en1, от aman_naughty, 2019-07-07 21:31:41

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

Теги #interview, #dp, divide and conquer, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)