Eat Pizza

Given an array of pizza slice sizes. You and a friend are competing to get the most pizza.

The rule is you can pick from either end of the pizza.

You can choose left or right side.

Your friend is greedy. He will always choose the side with a bigger slice.

Calculate the max amount of pizza you can get.

ex:[1, 2, 10, 4, 3, 5, 6]

Your picks: 6 -> 3 -> 10 -> 1 = 20

Opponent picks: 5 -> 4 -> 2 = 11

Core Idea: DP looking two back

Similar to cut wood, treating this as a join problem is much easier than cutting it down.

Using a 2D table we can memoize what is the most pizza we can keep from a I -> J segment

The trick is since we do not control the action of our opponent, we have to look Two Back instead of one since the order is: my move -> opponent move -> my move.

Does that mean we have cover branching twice? No, we don't. The reason is the opponent move is actually determined by our move. All we choose is left or right slice. After that the opponent will always choose the bigger slice after.

func pizza() {
  input := []int{1,2,100,4,3,5,6}

  M := make([][]int, len(input))
  
  for i := range M {
    M[i] = make([]int, len(input))  
  }

  //base case: first 2 moves\
  
  //move 1
  for i := range M {
    M[i][i] = input[i]
  }

  //move 2
  for i := 0; i + 1 < len(M); i++ {
    M[i][i+1] = max(M[i][i], M[i+1][i+1])
  }

  //Decisions:
  
  //pick i aka. left
  //opponent picks 
  //i + 1 : we get input[i] + M[i + 2][j]
  //or
  //j : we get input[i] + M[i + 1][j - 1]

  //pick j aka. right
  //opponent picks
  //j - 1: we get input[j] + M[i][j - 2]
  //or
  //i : we get input[j] + M[i + 1][j - 1]

  for offset := 2; offset < len(M); offset++ {
    for i := 0; i + offset < len(M); i++ {
      j := i + offset
      var left int
      if input[i+1] > input[j] {
        left = input[i] + M[i + 2][j]
      } else {
        left = input[i] + M[i + 1][j - 1]
      }
      right := input[j]
      if input[i] > input[j - 1]{
        right += M[i + 1][j - 1]
      } else {
        right += M[i][j - 2]
      }
      M[i][j] = max(left, right)
    }
  }

  fmt.Printf("the final answer is:    %d", M[0][len(M) - 1])
}

TC: O(N^2)

SC: O(N^2)