LIKE CODING: MJ [46] Find Maximal Selection in 3n Numbers

LIKE CODING: MJ [46] Find Maximal Selection in 3n Numbers
Given 3n numbers placed in a circle, you and two of your friends are playing a game. Each time you pick a number first, then the two neighboring numbers of the one you picked are picked by your friends. All the picked numbers are removed from the circle and the left numbers compose a new circle. This game terminates when all the numbers are removed.
Write a program to find the maximum sum of the numbers you picked.

Eg, if nums = {1,2,3}, it returns 3
       if nums = {1,2,3,4,5,6}, the first run you choose 6 and your friends choose 5 and 1. then nums = {2,3,4}. The 2nd run you choose 4. Thus, it returns 4+6=10;

Problem: How to write a DP solution?

    int getMaxin3n_rec(vector<int> nums){

        int n = nums.size();

        if(n==3){

            return max(max(nums[0], nums[1]), nums[2]);

        }else{

            int m = INT_MIN;

            for(int i=0; i<n; ++i){

                int v = nums[i], l = (i-1+n)%n, r = (i+1)%n;

                vector<int> vec;

                for(int j=0; j<n; ++j){

                    if(j!=i && j!=l && j!=r) vec.push_back(nums[j]);

                }

                m = max(m, getMaxin3n_rec(vec)+v);

            }

            return m;

        }

    }

 

};

http://www.mitbbs.com/article_t1/JobHunting/32961687_0_1.html
Read full article from LIKE CODING: MJ [46] Find Maximal Selection in 3n Numbers