2· [10 marks] Call a subset S of { 1,2, ,n) nonadjacent if it does not contain t
ID: 3605126 • Letter: 2
Question
2· [10 marks] Call a subset S of { 1,2, ,n) nonadjacent if it does not contain two consecutive integers. More precisely, a subset is nonadjacent ifE s implies that Given an array A[1..n] of n integers, the maximum nonadjacent sum problem asks for the maximum value of 8eSAsj, where s is a nonadjacent subset For example, if A[L·6] 2,-5, 7,6,0,5], then the maximum nonadjacent sum is 14, which comes from S = {1,3,6} Design an dynamic programming algorithm to compute the maximum nonadjacent sum of the array A.Explanation / Answer
This problem can be solved in O(n) using dynamic programming. As is typical for developing a dynamic-programming algorithm, we begin by (1) characterizing the structure of an optimal solution and (2) defining a recursive solution. To begin our design, note that the first element A[1] is either included in S or it is not. If it is included, then we cannot include A[2], however we must include the Maximum Non-consecutive Sum (MNCS) for A[3, . . . , n]. If A[1] is not in the MNCS, then we must include the MNCS for A[2, . . . , n]. By induction, a simple recursive algorithm for computing the MNCS is apparent. Beginning at the first element of A, we can recursively compute the MNCS for A[2, . . . , n] and A[3, . . . , n]. If A[1] plus the MNCS for A[3, . . . , n] is greater than or equal to the MNCS for A[2, . . . , n], then the first element must be included in S, otherwise it is not. We can proceed through the array elements, performing similar comparisons, to determine the elements of the subset S and the MNCS. We can greatly improve upon the naive solution by applying the dynamic programming. Note that M[1] is equal to the Maximum Non-consecutive Sum. for the subarray A[i, . . . , n].
The construction of M is implemented on lines 2-12 of Find-MNCS shown below. By the definition of M, the Maximum Non-consecutive Sum for the array A[1, . . . , n] is given by M[1] (as assigned on line 13). Note that, since we also want to know the elements of S in addition to the value of the MNCS, lines 15-21 traverse M and construct the optimal solution for S. Finally, the subset S and MNCS T are returned on line 22.
Find-MNCS(A)
1 Compute the lookup table M
2 n length[A]
3 M[n + 1] 0
4 if A[n] > 0
5 then M[n] A[n]
6 else M[n] 0
7 for i (n 1) downto 1
8 do if A[i] > 0
9 then S1 A[i] + M[i + 2]
10 else S1 0
11 S2 M[i + 1]
12 M[i] max(S1, S2)
13 T M[1]
14 Determine elements in subset S
15 S
16 i 1
17 while i n
18 do if M[i] > M[i + 1]
19 then S S i
20 i i + 2
21 else i i + 1
22 return S and T
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.