> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/eat-pizza.md).

# 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*.

```go
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)