楼上的看起来比较elegant，我随笔写的，不知道对错啊...
// assume A picks first, return difference between what A picks and what B
picks.
int pickNumber(int* array, int begin, int end, HashTable* hashTable) {
int result;
if (getFromHash(hashTable, begin, end, &result)) {
return result;
}
if (end == begin) {
putToHash(hashTable, begin, end, -array[begin]);
return -array[begin];
}
int diff1 = pickNumber(array, begin + 1, end);
int diff2 = pickNumber(array, begin, end + 1);
if ((end - begin) % 2) { // A is picking
if (diff1 + array[begin] > diff2 + array[end]) {
return diff1 + array[begin];
} else {
return diff2 + array[end];
}
} else {
if (diff1 + array[begin] > diff2 + array[end]) {
return diff2 + array[end];
} else {
return diff1 + array[begin];
}
}
}
