略譯

原題目連結

給你 n 棟建築的高度與寬度
分別求高度嚴格遞增子序列的寬度總和最大
與高度嚴格遞減子序列的寬度總和最大，分別是多少

題解

LIS 變形，不求序列長度，而是序列的寬度總和，
不過解法差不多

狀態以 dp[i] 記錄以第 i 棟為結尾的遞增序列，
其寬度總和最大為何

則對於前 i-1 棟中，所有高度小於第 i 棟的建築 k，
dp[i] = max(dp[k]) + w[i]

遞減依此類推

實作提示

• 無