求数组b的最长不减子序列长度

        从数组的第0个元素开始，顺序考察数组的每个元素，当数组的全部元素都被考察后才能求出数组的最长不减子序列。

设数组为b，已考察了b[0]~b[i-1]的全部元素，求得当前最长的不减子序列长为k。当前正要考察b[i]是否会引起k值的增大，取决于b[i]是否会大于或者等于b[0]~b[i-1]中某个最长不减子序列的终元素。但需要注意，b[0]~b[i-1]中可能有多个长为k的不减子序列。很显然，在同样长度的不减子序列中，只要保留终元素最小的那个子序列就足够了。若用一个变量保存b[0]~b[i-1]中长度为k的不减子序列的最小终元素，这样在b[0]~b[i-1]中，是否有长度为k+1的不减子序列，取决于b[i]是否大于或者等于那个变量。

        当b[i]小于长度为k的不减子序列的最小的终元素的值时，此时不能通过与该序列组成长度为 k + 1的不减子序列；如果在b[0]~b[i-1]中有长度为k-1的不减子序列，且该子序列的值不大于b[i]，这是因长度为k-1的不减子序列的终元素值小于等于b[i]，就得到一个终元素更小（因为没有一个长度为 k 的不减子序列的终元素小于 b[i]）的长度为k的不减子序列。

        为能发现上述可能，就得保留长度为k-1的不减子序列的终元素。依此类推，为保留长为k-2,k-3等的不减子序列，相应地也要为他们保留终元素的值。为此要引入一个数组，设为数组a，其第j个元素a[j]存放长为j的不减子序列的终元素的值。显然，数组a中的元素也是不减的序列。利用这个性质，在考察b[i]时，就能知道a中的哪个元素需要改变。从最长子序列至最短子序列顺序查找终元素小于等于b[i]的长为j的子序列，因b[i]大于等于长为j的不减子序列的终元素，找到了一个终元素更小的长为j+1的不减子序列，用b[i]作为长为j+1的子序列的终元素。当j的值为k时，已为长为k+1的子序列设定了终元素，这时最长不减子序列的长度k应增1。

最后

以上就是无语手链为你收集整理的求数组b的最长不减子序列长度的全部内容，希望文章能够帮你解决求数组b的最长不减子序列长度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。