0
$\begingroup$

I am trying to design an algorithm that computes the largest (by sum) contiguous subarray of an array of size n that uses a divide and conquer approach, but runs in linear time. The standard divide and conquer approach runs in O(nlogn) (can be found in chapter 4 of CLR) which is not what I am looking for. The following describes an O(n) divide and conquer algorithm: Page 16 https://software.intel.com/sites/default/files/m/d/4/1/d/8/10.1.1.150.7202.pdf however it goes over my head a little. Would anyone be able to shed some light on it?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.