Number Game Algorithm

Posted by 7Aces on Programmers See other posts from Programmers or by 7Aces
Published on 2012-11-06T18:47:17Z Indexed on 2012/11/06 23:18 UTC
Read the original article Hit count: 233

Filed under:

Problem Link - http://www.iarcs.org.in/inoi/2011/zco2011/zco2011-1b.php

The task is to find the maximum score you can get in the game. Such problems, based on games, where you have to simulate, predict the result, or obtain the maximum possible score always seem to puzzle me.

I can do it with recursion by considering two cases - first number picked or last number picked, each of which again branches into two states similarly, and so on... which finally can yield the max possible result.

But it's a very time-inefficient approach, since time increases exponentially, due to the large test cases.

What is the most pragmatic approach to the problem, and to such problems in general?

© Programmers or respective owner

Related posts about algorithms