dp_caching_1.cpp

static int INF = 1e9+7;
static int N = 0;
static vector<int> nums;
static int cache[100001][2];

static void init(vector<int>& prices) {
    N = size(prices);
    nums.resize(N);
    for (int i = 0; i < N; ++i) {
        nums[i] = prices[i];
        cache[i][0] = cache[i][1] = -1;
    }
}

static int run(int idx, int taken) {
    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[idx]);
    return cache[idx][taken] =  max(run(idx + 1, 0), -nums[idx] + run(idx + 1, 1));
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        init(prices);
        return run(0, 0);
    }
};