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/ however it goes over my head a little. Would anyone be able to shed some light on it?


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.