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 and acknowledge you have read our privacy policy.