There is a row of n items, numbered from 1 to n. Each item has an integer

value: item i has value A[i], where A[1...n] is an array. You wish to pick some

of the items but you cannot pick two adjacent items (that is, you cannot pick

both items i and i + 1 for any i). Subject to this constraint, you wish to

maximise the total sum of values of the items you have picked.

(a) [2 marks] Provide a counterexample to show that it is not always optimal

to pick the largest item.

(b) [3 marks] Provide a counterexample to show that the optimal solution

may require selecting a combination of odd and even numbered elements.

(c) [10 marks] Give an O(n) algorithm that determines this maximum total

sum of values.