作者pinglunliao (王者：一条孤独的不归路)
看板Prob_Solve
标题最长递增子序列
时间Thu Nov 16 00:30:01 2006
题目：
假设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
1F：推 LPH66:但你不能保证前三个就一定是你要的... 11/16 00:30
2F：推 pinglunliao:楼上的说到我的困难点，因为我是猜的，不知道怎麽证明 11/16 00:57
3F：→ pinglunliao:这个方法对不对。 11/16 00:58
4F：→ pinglunliao:想不出反例来 11/16 00:59
5F：推 Fenikso:5 3 1, 4 2 <= 不能取最大的 因为5 4不是递增 11/16 05:58
6F：推 march20:这是 DP 经典题, 把 A[1,1], A[1,2], A[1,n-1] 求完 11/16 16:34
7F：推 march20:A[1,n] 的解自然就冒出来了 11/16 16:35
8F：推 march20:啊, 不对, 其实要更麻烦点, 直接回文好了 11/16 16:36
9F：推 march20:漏看第二个条件了, 再重新想过 @@ 11/16 16:41