动态规划

AisDaeun 6 2023-10-29

线性DP

最长(非)严格上升子序列问题

O(n \log n)的解法:
设f[i]表示长度为i的子序列的末尾元素。
显然f具有单调性:长度越长,末尾元素必然越大。
对于严格上升子序列,\forall i < j, f[i] < f[j]
对于非严格上升子序列,\forall i < j, f[i] <= f[j]

非严格上升子序列:

	for (int i = 1; i <= n; i++) {
		if (a[i] >= f[len]) f[++len] = a[i];
		else {
			int pos = std::upper_bound(f + 1, f + len + 1, a[i]) - f;
			f[pos] = a[i];
		}
	}