A new swap$-$puzzle game involves n cute animals numbered from $1$ to n$.$ Each animal holds one

of three types of candies: fruity peanuts, cookie$-$and$-$cream bars, and birthday$-$cake truffles. You

also have a candy in your hand $$ at the start of the game, you have a fruity peanut.

To earn points in the game, you visit each of the n animals in order from $1$ to n$.$ For each animal,

you can either keep the candy in your hand or exchange it with the candy held by the animal.

$$ If you swap your candy for another candy of the same type, you earn one point.

$$ If you swap your candy for a candy of a different type, you lose one point.

$$ If you visit an animal and decide not to swap candy, your score does not change.

You must visit the animals in order, and once you visit an animal, you can never visit the animal

again.

Describe and analyze a dynamic programming algorithm to compute your maximum possible

score. Your input is array C$[1,...,$ n$],$ where C$[$i$]$ is the type of candy that the i$-$th animal is

holding.