Dynamic programming

In the SpacedSum problem, the input is an array A of n positive integers and the valid solution for this input is the largest possible value that can be obtained by summing a subset of the entries of

A such that the subset contains at most one of any two consecutives

entries A[i] ,A[i+ 1] for every 1 < i < n - 1

In this question, you will design and analyze a dynamic programming algorithm that solves the SpacedSum

problem.

(a) Provide an example to show that in some cases, the optimal solution can skip two consecutive entries in the array.

(b) Give an example to show that the greedy algorithm of choosing the entries in order of decreasing value (from largest to smallest while satisfying constrains) does not always give the best solution.

(c) Give a precise definition of a subproblem that can be used to solve the SpacedSum problem with a dynamic programming algorithm.

(d) Describe and justify the recurrence rule that will be used to compute the solutions to the subproblems defined in part (c).

(e) Provide the pseudocode for your dynamic programming algorithm that solves the SpacedSum problem using the subproblems and recurrence rule defined above.

(f) Analyze the time complexity of the algorithm obtained in part (e).