对斑竹:
斑竹的说法有一些不妥之处:
(1)认为代码就表示的算法,但是抽象算法的确是代码不能够替代的,因为同样的思想可能有不同的代码,只给代码的方法把问题给具体化了,而不是从一般的角度去考虑问题;
(2)认为注释和算法解释与可读性不相关的想法有些过于偏执了,如果知道某算法再看代码会轻松地多的.
再看问题,斑竹的代码中,不知道时候诸葛亮式的解答是否一定是最优解答,如果是有没有证明呢?
对楼主:
该问题是一类比较经典的动态规划题目最一般的算法为O(N^2),算法如下:
int d[MAX+1];//MAX为数据个数
状态d[i]记录了序列{a1,a2,a3....ai}的包含第i个数的最长不上升序列长,
//注意这是一个子问题{a1,a2,...ai}是原序列的一个子序列.
再看状态转移,我们从d[1]开始,显然d[1]=1,这时对应的序列{a1}只有1个数,假设在我们已经知道了d[1]到d[i]的值,怎么算d[i+1]的值呢,最长不上升序列中a[i+1]的前一个数,它可以是比a[i+1]大或相等前面任意一个数a[j],当然a[i+1]可能没有前驱,如果a[i+1]能够找到对应的a[j](a[j]可能不止一个)包含a[i]又包含a[j]的最长不上升序列长为(d[j]+1),即该序列为{a1,a2,a3..aj}的包含a[j]的最长不上升序列最后加上一个a[i+1],如果a[i+1]没有前驱,显然d[i+1]=1;
到现在为止可以写出状态转移方程:
d[i]=max{d[j]+1 (high[j]>=high[i]&&j<i) , 1 }
PS:
如果楼主看过动态规划算法的一些内容,那么应该对这个问题很熟悉:
最长公共子序列问题:
给出两个字符串,求它们的最长公共子序列长:
其实这个问题也可以转化到最长公共子序列问题:
即求:
a[1],a[2],a[3],....a[N]
b[1],b[2],b[3].....b[N] //{b[n]}为{a[n]}经过降序排序后得到的序列
最长公共子序列长:
PS2:楼主提出的问题可以利用树一类的辅助优化出(NlogN)的算法,有兴趣的话可以上网用:最长不上升序列为关键字查一下
[此贴子已经被作者于2006-6-21 7:28:57编辑过]