{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\"Roadies\" is back!!! In India, \"Roadies\" is a reality based tv show and is very popular among the youth.\u003c/p\u003e\r\n\u003cp\u003eThis time to get selected into \"Roadies\" they challenge you to solve the given problem... if you can solve it you will be selected!\u003c/p\u003e\r\n\u003cp\u003eChallenge is as follows: Suppose you are given an array with even number of integers. Player 1 and player 2 take turns to pick numbers, either the left-most element or the right-most element. You have to find the maximum possible score (sum of numbers chosen) by player 1. Assume player 1 always starts the game and plays optimally.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eNote\u003c/strong\u003e: when an element is picked it is removed from the array.\u003c/p\u003e\r\n\u003cp\u003eBut as usual this is \"Roadies\" hence cometh the twist. It is not known whether the second player is dumb or smart. As you know result will be different if player 2 is either dumb or smart.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eNOTE:\u003c/strong\u003e when player 2 plays like a dumb \u003cu\u003ethere is no fixed strategy of how he would choose the numbers\u003c/u\u003e i.e. he would choose the number either from start or end of an array without thinking... so there can be multiple answers possible when player 2 plays like a dumb...\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eSo you have to tell the maximum possible score of player 1 when player 2 plays dumb and smart.\u003c/strong\u003e\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eT: number of test cases (t \u0026lt; 20).\u003c/p\u003e\r\n\u003cp\u003eFor eact case two lines follow, first line contains the size of array (\u0026lt;\u003d 30) and next line contains the elements of the array.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each case print in new line two space separated integers: score when player 2 is dumb and score when player 2 is smart.\u003c/p\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4\r\n5 8 4 2\r\n4\r\n8 5 4 2\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13 10\r\n13 12\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003cp\u003e\u003cstrong\u003eNOTE\u003c/strong\u003e: All values will fit in int type.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eExplanation\u003c/strong\u003e: In first test case (when player 2 is dumb) then player 1 first chooses 5 then player 2 can choose 8 or 2 but chooses 2. so now player 1 can choose either 8 or 4 so chooses 8. Hence total score is 13.\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e(when player 2 is smart) player 1 can choose 5 or 2 but chooses 2 (so that player 2 cannot choose 8 in his turn) so now player 2 can choose 5 or 4. Irrespective of what player 2 chooses player 1 will have option to choose 8 in his next turn hence total (8 + 2) \u003d 10.\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}