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

dude can you please explain the algo rather than posting codes. That would help others. Code serves no need.

Nice code. Short and clear