Advertisement
RaFiN_

largest subarray sum using divide and conquer

Dec 20th, 2019
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.41 KB | None | 0 0
  1. the idea is: for each sub array we calculate 4 values in O(1) time based on the return values of its two halves. The meaning of the values:
  2.  
  3. l: the sum of the sub array with largest sum starting from the first
  4. element
  5. m: the sum of the sub array with largest sum
  6. r: the sum of the sub array with largest sum ending at the last
  7. element
  8. s: the sum of the whole array
  9. the recursive relation is clear in the code.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement