Order theory¶

Dilwoths's theorem: Suppose that the length of the longest antichain in the poset P is r, then P can be partitioned into r chains.

Dilworth's dual theorem: Suppose that the length of the longest chain in the poset P is r , then P can be partitioned into r antichains.

Erdős-Szekeres theorem: Given n ≥ rs + 1 , any sequence of n elements has either an increasing subsequence of length r+1 or a decreasing subsequence of lengthe s+1.

推薦這個影片講解非常清楚:

證明

其他相關資料:

material 1

material 2

material 3

遍歷逆序位置¶

在一堆上升區間中，快速的遍歷逆序的位置的優化方式。

用一個陣列儲存下次逆序位置。

• \(\text{nxt\_dec} [i]\) 指向當前上升區間的尾端。

vector<int> nxt_dec(n);
nxt_dec[n - 1] = n;
int p = n;
for(int i = n - 2; i >= 0; --i) {
    if(nums[i] > nums[i + 1]) p = i;
    nxt_dec[i] = p;
}