( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) figure tree of recursive calls when naively computing the th fibonacci numberf( each node is callf(xindicates call with argument xand the italicized numbers on the right are the sequence in which calls take place the children of node are the subcalls made by that call note how there are calls to ( )and calls to each of ( ) ( )and ( if < return f_minus_ f_minus_ for in range ( ) f_minus_ f_minus_ f_minus_ f_minus_ f_minus_ return f_minus_ the key to solving dp problem efficiently is finding way to break the problem into subproblems such that the original problem can be solved relatively easily once solutions to the subproblems are availableand these subproblem solutions are cached usuallybut not alwaysthe subproblems are easy to identify here is more sophisticated application of dp consider the following problemfind the maximum sum over all subarrays of given array of integer as concrete examplethe maximum subarray for the array in figure starts at index and ends at index - - - - [ [ [ [ [ [ [ [ [ figure an array with maximum subarray sum of the brute-force algorithmwhich computes each subarray sumhas ( time complexity- ( + there are subarraysand each subarray sum takes (ntime to compute the brute-force algorithm can be improved to ( )at the cost of (nadditional storageby first computing [ka[ kfor all the sum for [ijis then sjs[ ]where [- is taken to be here is natural divide-and-conquer algorithm take to be the middle index of solve the problem for the subarrays [ mand [ in addition to the answers for eachwe also return the maximum subarray sum for subarray ending at the last entry in land the maximum subarray sum for subarray starting at the first entry of the maximum subarray