I was solving THIS PROBLEM on top coder, it seemed very easy initially but when I solved it I realized it is not. Help me solving this problem. asked 10 Dec '16, 16:51

The question has been closed for the following reason "The question is answered, right answer was accepted" by vijju123 06 May '17, 16:17
We first solve the problem in a linear way and later extend it to take care of the circle case. Define the state Let S to be the set containing the optimal solution. Consider an element
The Base Cases go as 
Now we need to take care of the fact that the neighbourhood is circular. So, the 1st and the last people are neighbours. The simplest way to handle the circle case is to solve the problem twice. Once without including the last element (may or may not include first) and once without including the first element (may or may not include last element). The answer will be the maximum of the two as the optimal solution may contain either of the two or neither of the two. NOTE: Base cases will change depending on whether you are not including the first element or last element. Please upvote this if you find this helpful because I need it to ask questions. answered 10 Dec '16, 17:32

Just tweaking @samarjeet27's answer a bit You dont need the T(2) state.. change T(i) = max { a[i] + T(i  2), a[i  1] + T(i  3) } to T(i) = max { a[i] + T(i  2), T(i1) } I came here from the same Bad Neighbour problem on Topcoder And if you do by @samarjeet27's process. then You would need to put extra conditions as they said minimum no of inputs is 2. answered 06 May '17, 14:43
