which are then solved recursively this is the "dividepart the "conquerstage consists of patching together the two solutions of the subproblemsand possibly doing small amount of additional workto arrive at solution for the whole problem in our casethe maximum subsequence sum can be in one of three places either it occurs entirely in the left half of the inputor entirely in the right halfor it crosses the middle and is in both halves the first two cases can be solved recursively the last case can be obtained by finding the largest sum in the first half that includes the last element in the first halfand the largest sum in the second half that includes the first element in the second half these two sums can then be added together as an exampleconsider the following inputfirst half - - second half - - the maximum subsequence sum for the first half is (elements through and for the second half is (elements through the maximum sum in the first half that includes the last element in the first half is (elements through )and the maximum sum in the second half that includes the first element in the second half is (elements through thusthe maximum sum that spans both halves and goes through the middle is (elements through we seethenthat among the three ways to form large maximum subsequencefor our examplethe best way is to include elements from both halves thusthe answer is figure shows an implementation of this strategy the code for algorithm deserves some comment the general form of the call for the recursive function is to pass the input array along with the left and right borderswhich delimits the portion of the array that is operated upon one-line driver program sets this up by passing the borders and along with the array lines to handle the base case if left =rightthere is one elementand it is the maximum subsequence if the element is nonnegative the case left right is not possible unless is negative (although minor perturbations in the code could mess this uplines and perform the two recursive calls we can see that the recursive calls are always on smaller problem than the originalalthough minor perturbations in the code could destroy this property lines to and to calculate the two maximum sums that touch the center divider the sum of these two values is the maximum sum that spans both halves the routine max (not shownreturns the largest of the three possibilities algorithm clearly requires more effort to code than either of the two previous algorithms howevershorter code does not always mean better code as we have seen in the earlier table showing the running times of the algorithmsthis algorithm is considerably faster than the other two for all but the smallest of input sizes the running time is analyzed in much the same way as for the program that computes the fibonacci numbers let (nbe the time it takes to solve maximum subsequence sum problem of size if then the program takes some constant amount of time to execute lines to which we shall call one unit thust( otherwisethe