计算机等级考试C语言程序设计例解(04)

04.尝试从包含n个int数的数组中删除一些分量，以便所有剩余的分量形成一个不减的子序列。设计算法并编写程序来寻找数组的不减子序列的长度。
解决方案:
从数组的第一个元素开始，依次检查数组的每个元素。当数组的所有元素都被检查后，可以找到数组的最长子序列。设数组为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]是否大于或等于长度为k的未减子序列的最终元素值。
但是当b[i]小于长度为k的未减子序列的最小最终元素值时， 如果在b[0]到b[i-1]中有一个长度为k-1的未减子序列，并且这个子序列的值不大于b[i]，那么长度为k-1的未减子序列的最终元素值小于或等于b[i]。 为了找到上述可能性，必须保留长度为k-1的未减子序列的最后一个元素。以此类推，为了保持长度为k-2、k-3等的不减子序列。最后一个元素的值应该相应地为它们保留。为此引入一个数组变量，设置为数组a[]，其第j个元素a[j]存储长度为j的不减子序列最后一个元素的值，显然数组a[]中的元素也是不减序列。利用这个性质，我们可以知道当我们检查b[i]时，a[]中的哪个元素需要改变。从最长的子序列到最短的子序列，搜索长度为J的子序列。因为b[i]的最后一个元素大于或等于长度为j+1的未减子序列的最后一个元素，所以找到一个最后一个元素更小的未减子序列，将b[i]作为长度为j+1的子序列的终止元素。当j的值为k时，已经为长度为k+1的子序列设置了最后一个元素，然后最长的未减子序列长度k应该增加1。通过以上分析，求最长未减子序列长度的算法如下:
算法——求数组b的最长未减子序列长度[]
{
将最长未减子序列长度k设为1；
使用b[0]设置长度为1的子序列的终止元素；
for(I = 1；I {
按照子序列长度K到1的顺序，寻找最后一个元素小于或等于b[i]的长度为J的子序列；
使用b[i]作为长度为j+1的子序列的最后一个元素；
if(j = = k)k++；/*最长未减子序列长度k增加1*/
}
}