Given a list of n positive integers A=[a1,,an], we are looking for the largest neighboringproduct sum, which is defined as follows. Adjacent elements can be multiplied together (but don't have to) and then we sum up. Each element can be multiplied with at most one of its neighbors. Here are some examples. For A=[1,4,2,3,7,4,1], the max neighboring-product sum is 41=1+(42)+3+(74)+1 Note, in this example you cannot use something like (423) since 2 can get paired with at most one neighbor. For A=[2,2,1,3,2,1,2,2,1,2] the max neighboring-product sum is 19=(22)+1+(32)+1+ (22)+1+2 Hence, we pair some elements with one of their neighbors, these pairs are multiplied together, and then we add up the new numbers (either original unpaired elements or product of paired elements). Give an efficient dynamic programming algorithm to find the maximum neighboring product-sum. Please answer the following parts: 1. Define the entries of your table in words. E.g. T(i) or T(i,j) is ... 2. State a recurrence for the entries of your table in terms of smaller subproblems. Don't forget your base case(s). 3. Write pseudocode for your algorithm to solve this problem. 4. State and analyze the running time of your algorithm. Faster (and correct) solutions are worth more credit. Give a dynamic programming algorithm that finds the maximum value of neighboring-product sum