-
Notifications
You must be signed in to change notification settings - Fork 0
/
PredictTheWinner.java
24 lines (21 loc) · 1.59 KB
/
PredictTheWinner.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package dynamicProgramming;
/**Предсказание победителя. Первый игрок выбирает элемент с одного из концов массива, второй игрок следом выбирает один из
* оставшихся с краёв элементов. Процедура продолжается до тех пор, пока не останется невыбранных элементов.
* Первый игрок побеждает, если сумма его элементов не меньше, чем у второго игрока. Предполагается, что оба игрока
* действуют оптимальным образом.
* @author Сергей Шершавин*/
public class PredictTheWinner {
/**@return true если первый игрок победит, иначе - false*/
public boolean getTheWinner(int[] nums) {
if ((nums.length & 1) == 0) return true; /* в силу того, что при равенстве сумм элементов преимущество у
первого игрока, при оптимальной игре и чётном количестве элементов, первый игрок всегда побеждает*/
int[] dp = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = i; j < nums.length; j++) {
if (i == j) dp[i] = nums[i];
else dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j-1]);
}
}
return dp[nums.length-1] >= 0;
}
}