title: Facebook interview: find out the order that gives max sum by selecting boxes with number in a ring, when the two next to it is destroyed
body: <p>Didn't find any similar question about this.
  This is a final round Facebook question:</p>
  
  <p>You are given a ring of boxes. Each box has a non-negative number on it, can be duplicate.</p>
  
  <p>Write a function/algorithm that will tell you the order at which you select the boxes, that will give you the max sum.</p>
  
  <p>The catch is, if you select a box, it is taken off the ring, and so are the two boxes next to it (to the right and the left of the one you selected).</p>
  
  <p>so if I have a ring of<br>
  {10 3 8 12}</p>
  
  <p>If I select 12,  8 and 10 will be destroyed and you are left with 3.</p>
  
  <p>The max will be selecting 8 first then 10, or 10 first then 8.</p>
  
  <p>I tried re-assign the boxes their value by take its own value and then subtracts the two next to is as the cost.</p>
  
  <p>So the old ring is {10 3 8 12}</p>
  
  <p>the new ring is {-5, -15, -7, -6}, and I will pick the highest.</p>
  
  <p>However, this definitely doesn't work if you have { 10, 19, 10, 0}, you should take the two 10s, but the algorithm will take the 19 and 0.</p>
  
  <p>Help please?</p>
  
  <p>It is most likely dynamic programming, but I don't know how.</p>
  
  <p>The ring can be any size. </p>