program must perform two recursive callsthe two for loops between lines and and some small amount of bookkeepingsuch as lines and the two for loops combine to touch every element in the subarrayand there is constant work inside the loopsso the time expended in lines to is (nthe code in lines to and is all constant amount of work and can thus be ignored compared with (nthe remainder of the work is performed in lines and these lines solve two subsequence problems of size / (assuming is eventhusthese lines take ( / units of time eachfor total of ( / the total time for the algorithm then is ( / (nthis gives the equations ( ( ( / (nto simplify the calculationswe can replace the (nterm in the equation above with nsince (nwill be expressed in big-oh notation anywaythis will not affect the answer in we shall see how to solve this equation rigorously for nowif ( ( / nand ( then ( ( ( and ( the pattern that is evidentand can be derivedis that if then (nn ( log ( log nthis analysis assumes is evensince otherwise / is not defined by the recursive nature of the analysisit is really valid only when is power of since otherwise we eventually get subproblem that is not an even sizeand the equation is invalid when is not power of somewhat more complicated analysis is requiredbut the big-oh result remains unchanged in future we will see several clever applications of recursion herewe present fourth algorithm to find the maximum subsequence sum this algorithm is simpler to implement than the recursive algorithm and also is more efficient it is shown in figure it should be clear why the time bound is correctbut it takes little thought to see why the algorithm actually works to sketch the logicnote that like algorithms and is representing the end of the current sequencewhile is representing the start of the current sequence it happens that the use of can be optimized out of the program if we do not need to know where the actual best subsequence isbut in designing the algorithmlet' pretend that is needed and that we are trying to improve algorithm one observation is that if [iis negativethen it cannot possibly be the start of the optimal subsequencesince any subsequence that begins by including [iwould be improved by beginning with [ + similarlyany negative subsequence cannot possibly be prefix of the optimal subsequence (same logicifin the inner loopwe detect that the subsequence from [ito [jis negativethen we can advance the crucial observation is that not only can we advance to + but we can also actually advance it all the way to + to see thislet be any index between + and any subsequence that starts at index is not larger than the corresponding subsequence that starts at index and includes the subsequence from [ito [ - ]since the latter subsequence is not negative ( is the first index that causes the subsequence starting at index to become negativethusadvancing to + is risk freewe cannot miss an optimal solution this algorithm is typical of many clever algorithmsthe running time is obviousbut the correctness is not for these algorithmsformal correctness proofs (more formal