A well-known problem is finding Longest Common Subsequence (LCS) of 2 strings , let's say string A and string B. If |A| ≤ 5000, |B| ≤ 10⁶ then we cannot use the simple dynamic programming approach since its complexity would be O(|A|.|B|).

One observation is that, the length of LCS is indeed ≤ min(|A|, |B|). Then, instead of letting dp[i][j] = k be the longest LCS when we consider first i characters of A and first j characters of B, we will let dp[i][k] = j meaning j is the smallest position in B so that it can form a LCS of length k with first i characters of A.

This requires a pre-processed array next[i][j] meaning the first position of character j in [i..|B|]. However, the complexity for DP now is reduced to O(|A|²).

Nice one.

Given an array of n ≤ 10⁶ positive integers, output the number of non-empty subsequences whose sum is divisible by a given 2 ≤ m ≤ 300, modulo 1000003. You may try it here.

Weights and Measures

The nlogn optimization for longest increasing subsequence swaps the state and value, optimizing for the smallest last value that has a certain length.

This is described here: https://en.wikipedia.org/wiki/Longest_increasing_subsequence