求最长单调递增子序列

问题描述

设计一个时间的算法，找出由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;
} 

 

算法复杂度分析（时间、空间）

1.分析程序中循环嵌套最多语句：

for(int i=n-1;i>=0;i--)

    for(int j=i+1;j<n;j++)   

       ……

易得程序的时间复杂度为。

2.空间复杂度为。程序执行过程中开辟了一个大小为n的自定义数组(相当于两个大小为n的整型数组)、定义了若干整型变量且无递归调用，故空间复杂度为。