首页 > > 程序设计 > C/C++ >

求最长单调递增子序列

2018-12-04 07:14:26来源：博客园阅读 ()

问题描述

设计一个时间的算法，找出由n个数组成的最长单调递增子序列。

算法描述

外层循环从右至左，内层循环从当前单元到最后一个单元。
在内层循环中，如果有单元大于当前单元且它的子序列长度大于当前记录的子序列长度，则用max记录当前单元找到最长的子序列长度。
遍历数组Order，找到order最大的单元，并将它的order值赋给max，它的num值赋给fore。fore即为最长单调递增子序列的第一个数据，max即为最长单调递增子序列的长度。
遍历数组Order，当当前单元的order等于max且当前单元的num大于等于fore时，输出当前单元的num，将max减1，fore赋值为当前单元的num。
这样得到的单调递增子序列必为最长单调递增子序列或最长单调递增子序列之一（当有多个长度相同的最长单调递增子序列时）。

算法实现

#include<stdio.h>
struct Date
{
    int num;
    int order;
};
void ascorder(struct Date *a,int n)
{   //寻找最长单调递增子序列
    for(int i=n-1;i>=0;i--)//从数组最后一个到第一个
    {
        int max=0;
        for(int j=i+1;j<n;j++)//从当前单元到数组最后一个单元
        {
            if((a[j].num>a[i].num)&&(a[j].order>max))
            //如果有单元大于当前单元且它的子序列长度大于当前记录的子序列长度
            {
                max=a[j].order;//记录当前单元找到最长子序列长度
                a[i].order=a[j].order+1;//更新当前单元的order
            }
        }
    }
    //输出最长单调递增子序列  
    //找到最长单调递增子序列开始的单元
    int max=0;
    int fore;
    for(int i=0;i<n;i++)
        if(a[i].order>max)
        {
            max=a[i].order;
            fore=a[i].num;
        }
        //依次输出序列中的单元    
        for(int i=0;i<n;i++)
        if((a[i].order==max)&&(a[i].num>=fore))
        {
            printf("%d ",a[i].num);
            max--;
            fore=a[i].num;
        }  
}
int main()
{
    struct Date a[15]={7,1,6,1,5,1,4,1,16,1,
                       5,1,14,1,9,1,10,1,90,1,
               15,1,19,1,20,1,1,1,3,1};
    //自定义数组
    int n=15;
    ascorder(a,n);//求解最长单调递增子序列算法
    return 0;
}