解題思路:
觀察題目,我們需要找出某種依照 x 、 y 遞增的序列,
但不需要找出序列本身,只需要知道其長度即可。
當想到遞增子序列、求長度後,很容易發現可以利用 LIS 實作。
LIS 就是所謂的最長遞增子序列 (Longest Increasing Subsequence) ,
其最高效的一種解法,是利用二分搜,在迭代過程中,逐步選取並汰換已選擇元素,
令所選的子序列保持在最適合遞增的狀態。
這種演算法無法得知真正的 LIS 本身,僅能得知長度。
實作策略:
由於測資給予的座標點並未經過排序,
若我們直接對 x 或 y 單獨做 LIS ,有可能選到回頭的路徑,
也就是可能會確保了 x 的遞增,卻選到了 y 減少的座標。
為此,我們只需要先針對 x 或 y 做好排序,
再對另一者做 LIS ,即可求出答案。