We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
O(N) Solution:
Reverse the original array
Make an array sum which stores sum until ith element
Make a 1D dp array. For each game the maximum sum a player can get is Sum[i] - (the sum other player can get in the remaining bricks) i.e. maximum of (sum[i] - dp[i-1] (selecting only one brick), sum[i]- dp[i-2] (2 bricks), sum[i] - dp[i-3] (3 bricks))
Take care of base cases
Bricks Game
You are viewing a single comment's thread. Return to all comments →
O(N) Solution: Reverse the original array Make an array sum which stores sum until ith element Make a 1D dp array. For each game the maximum sum a player can get is Sum[i] - (the sum other player can get in the remaining bricks) i.e. maximum of (sum[i] - dp[i-1] (selecting only one brick), sum[i]- dp[i-2] (2 bricks), sum[i] - dp[i-3] (3 bricks)) Take care of base cases