Hi All,
I came across the following problem recently and could not figure out an efficient way to solve it (other then backtracking). Can anyone please help.
Problem Statement:
A circular cake has 3*N slices. Each slice has a size given. Person X, on his birthday, has to eat the whole cake along with his friends Y and Z. Because its X's birthday, he is made to choose a slice everytime, and the slice immediate to the left and right of what X has picked will be picked by Y and Z. What is the maximum cake X can eat?
Given: An array representing the cake slice size.
Example 1: Input: {4,8,3} Output : 8
Explanation: X will simply pick 8
Example 2: Input: {6,11,14,22,20,3} Output: 34
Explanation: X will pick 14 & 20 sized slices
Example 3: Input: {14,11,6,3,22,20} Output: 36
Explanation: X will pick 14 & 22 sized slices.
Note: X cannot pick 14 & 20 as they are adjacent.
Thanks
Full text and comments »