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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
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