dp_caching_2.cpp

static int INF = 1e9+7;
static int cache[100001][2];

static int run(int idx, int taken, vector<int>& nums) {
    const int N = size(nums);
    if (idx == N and taken == 1) return -INF;
    if (idx == N) return 0;
    if (cache[idx][taken] != -1) return cache[idx][taken];
    if (taken) return cache[idx][taken] = max(
        run(idx + 1, 1, nums),
        nums[idx]
    );
    return cache[idx][taken] =  max(
        run(idx + 1, 0, nums),
        -nums[idx] + run(idx + 1, 1, nums)
    );
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        memset(cache, -1, sizeof(cache));
        return run(0, 0, prices);
    }
};