題意

• 有一排大樓，高度依序為 h1,h2,…,hn。

• 滑翔表演要從某棟大樓開始，往右邊滑翔。

• 為了安全，滑翔路徑的高度必須 嚴格遞減（每次滑到的下一棟大樓都要比前一棟矮）。

• 問你：可以找到的 最長滑翔路徑 長度是多少？

換句話說，就是：
在數列 h1,h2,…,hn裡，找一個往右、嚴格遞減的最長子序列（Longest Decreasing Subsequence, LDS），但是這個子序列必須連續往右（不能往左，也不能跳回去）。

思考

這題跟 最長嚴格遞減子序列 很像，但有個限制：

• 只能朝右滑翔，所以我們不是找「任意子序列」，而是找「從左到右的連續路徑」。

更準確說法：
對於每個大樓 i，我們可以嘗試從它開始，一直往右找比它低的樓，組成一條遞減路徑，直到不能繼續為止。然後取所有路徑中的最長。

演算法

其實這就是典型的 動態規劃（DP） 問題。
我們可以定義：

dp[i]=以第i棟大樓作為起點時，能走出的最長滑翔路徑長度dp[i] = 以第 i 棟大樓作為起點時，能走出的最長滑翔路徑長度dp[i]=以第i棟大樓作為起點時，能走出的最長滑翔路徑長度

轉移方式：

• 從 i 之後的所有大樓 j (j>i) 中，如果 h[j]<h[i]，
  那麼我們可以往 j 前進，於是：

dp[i]=1+max⁡(dp[j]) (其中 h[j]<h[i])

• 如果沒有比 h[i]矮的樓，那麼：

dp[i]=1

最後答案就是：

max⁡(dp[i])for all i

程式碼範例 (Python)