HACKER RANK: Play Game

Problem Link: https://www.hackerrank.com/challenges/play-game

Summary:
Given N number of elements in stack.

first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Print a single line containing your maximum score.

For Example:

Sample Input:

2

5

999 1 1 1 0

5

0 1 1 1 999

Sample Output:

1001

999

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:

I took dp[2][n]

dp[0]->My Score

dp[1]->Minimum Score other player leaves for me as he also play optimally

When n = 1,2,3 then you took all elements in stack

dp[0][n-1]=a[n-1]

dp[0][n-2]=a[n-1]+a[n-2]

dp[0][n-3]=a[n-1]+a[n-2]+a[n-3]

so for i n-4 to 0:

    dp[1][i] = min(dp[0][i+1],min(dp[0][i+2],dp[0][i+3]))

    dp[0][i] = max(a[i]+dp[1][i+1],max(a[i]+a[i+1]+dp[1][i+2],a[i]+a[i+1]+a[i+2]+dp[1][i+3]))

ans = dp[0][0]

print ans

In this code dp[1][i] is minimum left by other player for you when he plays optimally i.e chooses maximum sum of elements for itself.

and dp[0][i] is maximum of taking one element, two element or three element plus minimum left by other player when he chooses maximum sum of elements for itself.

Time Complexity: O(n)

To View My Solution:

https://github.com/shivam04/hackerrank/blob/master/play-game.cpp