Maximum possible score by player 1

Problem: Link

Suppose you are given an array with even number of integers. You and some other player take turns to pick numbers, either the leftmost element or the rightmost element. We have to find the maximum possible score (sum of numbers chosen) by player 1.
For example: if array is 5 8 4 2, then player 1 can choose either 5 or 2. Suppose he chooses 2, then player 2 can choose 5 or 4. Irrespective of what player 2 chooses, in next round player 1 will have chance to choose 8. Thus, maximum possible score by player 1, in this scenario, is (8+2)=10.

Solution:

#include <stdio.h>

#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)

/* Returns maximum possible score of player1 incase of player2 is dumb */
int maxscoredumb(int a[], int start, int end)
{
if(start > end)
return 0;

if(start == end - 1)
{
return max(a[start], a[end]);
}
else if(start == end)
{
return a[start];
}

/* if player1 chooses left */
int left = a[start];
{
int left1 = maxscoredumb(a, start + 2, end); //if player2 chooses start
int left2 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses end

left += max(left1, left2); //assuming player2 is dumb, if player2 is smart, we have to take min
}

/* if player1 chooses right */
int right = a[end];
{
int right1 = maxscoredumb(a, start + 1, end - 1); //if player2 chooses start
int right2 = maxscoredumb(a, start, end - 2); //if player2 chooses end

right += max(right1, right2); //assuming player2 is dumb, if player2 is smart, we have to take min
}

return max(left, right);
}


/* Returns maximum possible score of player1 incase of player2 is smart */
int maxscoresmart(int a[], int start, int end)
{
if(start > end)
return 0;

if(start == end - 1)
{
return max(a[start], a[end]);
}
else if(start == end)
{
return a[start];
}

/* if player1 chooses left */
int left = a[start];
{
int left1 = maxscoresmart(a, start + 2, end); //if player2 chooses start
int left2 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses end

left += min(left1, left2);
}

/* if player1 chooses right */
int right = a[end];
{
int right1 = maxscoresmart(a, start + 1, end - 1); //if player2 chooses start
int right2 = maxscoresmart(a, start, end - 2); //if player2 chooses end

right += min(right1, right2);
}

return max(left, right);
}
int main()
{
int n;

scanf("%d", &n);

int a[n];

int i;

for( i = 0; i < n; ++i)
scanf("%d", a + i);

printf("Player2 Dumb: %d\n", maxscoredumb(a, 0, n-1));
printf("Player2 Smart: %d\n", maxscoresmart(a, 0, n-1));
Advertisements

2 thoughts on “Maximum possible score by player 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s