C++——最长递增子序列问题【组合问题中的动态规划】

代码语言：javascript复制

#include <iostream>
//动态规划法:最长递增子序列之和
int IncreaseOrder(int a[],int n);
using namespace std;

int main()
{
    int n;
    cout<<"请输入数组长度:";
    cin>>n;
    int a[n];
    int i;
    cout<<"请输入数组元素:"<<endl;
    for(i=0; i<n; i  )
        cin>>a[i];
    for(i=0; i<n; i  )
        cout<<a[i]<<" ";
    cout<<endl;
    int len = IncreaseOrder(a,n);
    cout<<endl;
    cout<<"最长子序列长为"<<len<<endl;
    cout << "Hello world!" << endl;
    return 0;
}
int IncreaseOrder(int a[],int n)
{
    int i,k,j,index;
    int L[10],x[10][10];
    for(i=0; i<n; i  )     //初始化，长度为一
    {
        L[i]=1;
        x[i][0] = a[i];
    }
    for(i=1; i<n; i  )    //依次计算a[0]~a[i]的最长递增子序列
    {
        int max=1;
        for(j=i-1; j>=0; j--)   //初始化递增子序列长度最大值
        {
            if((a[j]<a[i])&&(max<L[j] 1))
            {
                max=L[j] 1;
                L[i]=max;
                for(k=0; k<max-1; k  )     //存储最长递增子序列
                    x[i][k]=x[j][k];
                x[i][max-1]= a[i];
            }
        }
    }
    for(index=0,i=1; i<n; i  )   //求所有递增子序列的最大长度
        if(L[index]<L[i]) index=i;
    cout<<"最长递增子序列是:";
    for(i=0; i<L[index]; i  )   //输出最长递增子序列
        cout<<x[index][i]<<" ";
    return L[index];            //返回值：最长递增子序列长度
}

c++ 动态规划

0 人点赞