Dynamic Programming ( Classics )

Subarray sums

Max/min sum subarray ( trivial )

int maxSubArray(vector<int>& nums) {
    int curs = nums[0], mx = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        curs = max(nums[i], curs + nums[i]);
        mx = max(curs, mx);
    }
    return mx;
}

Max/min sum circular subarray ( complement of min trick )

A wrong idea is to use virtual indexing and duplicating the array, note that that’s just wrong since the subarray can’t be longer than n, but with this you might take >n elements.

int maxSubarraySumCircular(vector<int>& nums) {
    int cur_max, cur_min, mx, mn, tot;
    cur_max = cur_min = mx = mn = tot = nums[0];
 
    for (int i = 1; i < (int)nums.size(); i++) {
        int elem = nums[i];
        cur_max = max(cur_max + elem, elem);
        cur_min = min(cur_min + elem, elem);
        tot += elem;
        mx = max(mx, cur_max);
        mn = min(mn, cur_min);
    }
    // note that mn can be the entire array so on complement this can be empty array
    if (mn == tot) mn = (int)(1e9);
    return max(mx, tot - mn);
}

Longest Increasing Subsequence 2

Link: https://leetcode.com/problems/longest-increasing-subsequence-ii/

LIS such that the difference between adjacent elements is at most k. Limitation: Values are small so I can think in terms of a dp not on indices but on values ( or since it’s increasing you can do coordinates compression but the dp on values is hint ).

This variation uses a segment tree.

$$\begin{array}{rl}f(v)& =lengthoflongestincreasingsubsequenceendingwithvaluev\\ f(v)& =max(1,ma{x}_{u\in [v-k,v-1]}(f(u)+1))\end{array}$$

Query the segment tree for the range [v-k, v-1] to get the maximum f(u) in that range.