StoneII

class Solution {
    public:
    //this function returns the maximium alex can gain
    typedef struct {
        int maxAlex;
        int maxLee;
    } rt;


    unordered_map<string, rt> memo;

    rt h_stoneGameII(vector < int > & piles, int index, int M, int chance) {
        string key = to_string(index) + "|" + to_string(M) + "|" + to_string(chance);
        if(memo.count(key)){
            return memo[key];
        }

        rt to_return;
        int upperX = 2 * M;

        to_return.maxAlex = 0;
        to_return.maxLee = 0;
        if (piles.size() - index <= upperX) {
            int sum = 0;
            for (int i = index; i < piles.size(); i++) {
                sum += piles[i];
            }

            if (chance == 0) {
                to_return.maxAlex = sum;
                to_return.maxLee = 0;
            } else {
                to_return.maxAlex = 0;
                to_return.maxLee = sum;
            }
            memo[key] = to_return;
            return to_return;
        }

        int alexCount = 0;
        int leeCount = 0;

        for (int i = index; i < index + upperX; i++) {
            if (chance == 0) {
                //i.e alex is choosing
                alexCount += piles[i];
                rt maxGettingNow = h_stoneGameII(piles, i + 1, max(i-index+1, M), 1);
                if(alexCount + maxGettingNow.maxAlex > to_return.maxAlex){
                    to_return.maxLee = maxGettingNow.maxLee;
                    to_return.maxAlex = maxGettingNow.maxAlex + alexCount;
                }
            } else {
                //i.e lee is choosing
                leeCount += piles[i];
                rt maxGettingNow = h_stoneGameII(piles, i + 1, max(i-index+1, M), 0);
                if(leeCount + maxGettingNow.maxLee > to_return.maxLee){
                    to_return.maxLee = maxGettingNow.maxLee + leeCount;
                    to_return.maxAlex = maxGettingNow.maxAlex;
                }
            }
        }
        memo[key] = to_return;
        return to_return;
    }

    int stoneGameII(vector < int > & piles) {
        return h_stoneGameII(piles, 0, 1, 0).maxAlex;
    }
};