最長遞增子序列

[pinglunliao (王者：一條孤獨的不歸路)]

題目：
假設A是一含有N個相異整數的陣列。試設計一程式找出A中最長遞增子序列(Longest
increasing subsequence) ，

若有兩個解以上，則輸出總和為最大的那一組。

例如A中元素值若為 7，6，23，24，20，18，22 則其最長遞增子序列為

7 23 24、6 23 24、7 18 22

7 20 22、6 18 22、6 20 22

總和最大是 7 23 24 這一組。

底下是我的想法：

先求出最長遞增子序列的長度為3(利用dynamic programming可求出)，再將序列切割成幾
個集合，每個集合內的元素都是遞減

7 6 | 23 | 24 20 18 | 22

從左到右分別對每個集合取最大值

7 6　　　　取最大的為 7
23 　　　　取最大的為 23
24 20 18　 取最大的為 24 ==> 取了三個了，所以 7 23 24 為解

不知道這個方法對不對？

--
蟄伏秋山待楓紅，青臨洛水無雲彩
  麒麟降世多磨難，江郎願使盡長才。 <臥江子> 
http://www.wretch.cc/blog/pinglunliao/ 我目前常用的個人網誌
http://pinglunliao.blogspot.com/ 以前在用的
http://blog.yam.com/pinglunliao/ 申請好玩的
http://blog.xuite.net/pinglunliao/pinglunliao/ 快癈了！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.130.34.88
推 LPH66:但你不能保證前三個就一定是你要的...
推 pinglunliao:樓上的說到我的困難點，因為我是猜的，不知道怎麼證明
→ pinglunliao:這個方法對不對。
→ pinglunliao:想不出反例來
推 Fenikso:5 3 1, 4 2  <= 不能取最大的 因為5 4不是遞增
推 march20:這是 DP 經典題, 把 A[1,1], A[1,2], A[1,n-1] 求完
推 march20:A[1,n] 的解自然就冒出來了
推 march20:啊, 不對, 其實要更麻煩點, 直接回文好了
推 march20:漏看第二個條件了, 再重新想過 @@