Consider the following game. You are given a sequence of n positive numbers (a1, a2, ...,...

 $$

Transcribed Image Text:

Consider the following game. You are given a sequence of n positive numbers (a1, a2, ..., ,an). Initially, they are all colored black. At each move, you choose a black number ak and color it and its immediate neighbors (if any) red (the immediate neighbors are the elements ak-1, ak+1). You get ak points for this move. The game ends when all numbers are colored red. The goal is to get as many points as possible. (a) Describe a greedy algorithm for this problem. Verify that it does not always maximize the number of points by giving a counter-example. Consider the following game. You are given a sequence of n positive numbers (a1, a2, ..., ,an). Initially, they are all colored black. At each move, you choose a black number ak and color it and its immediate neighbors (if any) red (the immediate neighbors are the elements ak-1, ak+1). You get ak points for this move. The game ends when all numbers are colored red. The goal is to get as many points as possible. (a) Describe a greedy algorithm for this problem. Verify that it does not always maximize the number of points by giving a counter-example.

Answer rating: 100% (QA)

The image contains a problem statement about a game involving a sequence of positive numbers You are ... View the full answer