CODEWITHSUNDEEP
algorithm
Stephanie
Stephanie

Reputation: 71

Maximum contiguous sum using Divide and Conquer

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!

Upvotes: 1

Views: 707

Answers (1)

gcc
gcc

Reputation: 152

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).

Upvotes: 2

Related Questions