Given an array X of N real numbers we would like to find the maximum sum of entries found in any subarray of X. For instance, if N = 10 and X[1..10] is 1 2 3 4 5 6 7 8 9 10 31 -41 59 26 -53 58 97 -93 -23 84 then the answer is 187, which is the sum of entries 59, 26, -53, 58, 97 in the "maximum subarray" X[3..7]. The problem is easy when all the entries are positive -- the maximum subarray is the entire input vector. The rub comes when some of the numbers are negative: should we include a negative number in hopes that the positive numbers to its sides will compensate for its negative contribution? Of course, if the entries are all negative then the maximum subarray is the empty subarray and zero should be returned.Design this algorithm with backtracking