- 4 Given An Array A 1 N Of Positive Integers You Have To Select A Subset S With Maximum Sum From These Numbers In T 1 (82.33 KiB) Viewed 32 times
= 4. Given an array A[1..n] of positive integers, you have to select a subset S with maximum sum from these numbers in the array, such that no three consecutive numbers from A are selected for such a subset S. Give an O(n) algorithm for this problem using dynamic programming. For example, if A = {2,4,6, 5, 1, 3, 7,9} we cannot select S = {4,6,5, 7, 9} because that will have first three numbers which were consecutive in A. However, we can pick S = {2,4,5, 1,7,9} because this has no three consecutive numbers from A. But then this sum (28) is not the maximum possible. We could have instead chosen S = {2,6,5,7,9} which has sum of 29. = =