I got confused about "Use the divide-and-conquer approach to write an efficient recursive algorithm that finds the maximum sum in any contiguous sublist of a given list of n real (positive or negative) values."
I know how to solve the problem without using divide-and-conquer, but have no idea of using divide-and-conquer approach.
Appreciate for help!
Split the list l into two sublists l1,l2. Let l1_last, l2_first be the last element of l1 respectively first element of l2 (l2_first immediately follows l1_last in the list l).
Find s1a the maximum contiguous sum of a sublist l1a of l1 not containing l1_last and s1b the maximum contiguous sum of a sublist l1b of l1 containing l1_last.
Likewise do the same for l2, get s2a, l2a and s2b,l2b where l1_last is replaced with l2_first. The maximal contiguous sum of a sublist of l is the maximum of s1a, s1b, s2a, s2b, s1b+s2b with corresponding sublists l1a, l1b, l2a, l2b c(l1b,l2b).
