A sequence of numbers is bitonic if it increases initially and eventually starts to decrease. The maximum sum bitonic subsequence problem takes as input an array of numbers. The output is the maximum sum of any bitonic subsequence within the array.

For example, if A = [5,2,4,10,8,1,20,4,27,15] the optimal solution is 78, which results from the bitonic subsequence 2, 4, 10, 20, 27, 15.

Find a dynamic programming solution to this problem. Provide a recurrence relation for your solution and pseudo-code