Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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:
- l: the sum of the sub array with largest sum starting from the first
- element
- m: the sum of the sub array with largest sum
- r: the sum of the sub array with largest sum ending at the last
- element
- s: the sum of the whole array
- the recursive relation is clear in the code.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement