最长递增子序列数


难度级别 中等
经常问 亚马逊 Samsung 百会
排列 动态编程

问题陈述

问题“最长增加子序列数”指出给您一个大小为n的数组a []。 打印其中最长的递增子序列数。

最长递增子序列数

使用案列

a[ ] = {1, 2, 5, 4, 7}
2

说明:在以上图像中可以看到最长的递增子序列。

输入: a [] = {1,2,3,4,5}

输出: 1(1,2,3,4,5是此处最长的子序列)

最长递增子序列数的算法

  1. 初始化 排列 a []的 整数 尺寸类型
  2. 创建一个函数来查找编号 最长的递增子序列 它接受整数类型的数组,其大小作为参数。
  3. 创建两个大小为n的len和cnt的整数类型的数组,并将两个数组的每个元素初始化为1。此外,初始化一个整数变量lis = 1。
  4. 使用i从1遍历到n-1,并创建一个从0到i-1的内部循环。
  5. 检查外循环当前索引处数组a []中的元素是否大于内循环当前索引处数组a []中的元素,检查内循环当前索引处len []数组中的值+ 1 loop大于外部循环当前索引处的len []数组中的元素,将外部循环当前索引处的len []数组中的值更新为内部循环当前索引处的len []数组中的值+ 1外部循环当前索引处的cnt []数组中的值作为内部循环当前索引处的cnt []数组中的值。
  6. 否则,如果内层循环当前索引处的len []等于外层循环当前索引处的len []数组中的元素,如果数组中的值+ 1,则将外层循环当前索引处的cnt []数组中的值更新为内循环当前索引和外循环本身在数组cnt []中的值之和。
  7. 将lis和len [i]的最大值存储在lis中。
  8. 将变量ans初始化为0。
  9. 再次从0遍历到n-1,并检查len [i]是否等于lis,将其值添加到cnt的当前索引中,单位为ans。
  10. 返回ans。

代码

C ++程序查找增加最长的子序列的数量

#include <bits/stdc++.h>
using namespace std;

class Longestsubseq{
    public:
        int numOfIncSubseq(int a[], int n){
        
        int len[n], cnt[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[j]){
                
                    if(len[j]+1 > len[i]){
                        len[i] = len[j]+1;
                        cnt[i] = cnt[j];
                    }
                    
                    else if(len[j]+1 == len[i]){
                        cnt[i] += cnt[j];
                    }
                }
        
                lis = max(lis, len[i]);
            }
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            if(len[i] == lis)ans += cnt[i];
        }
        
        return ans;
    }
};

int main(){
    Longestsubseq ls;
    
    int a[] = {1,2,5,4,7};
    int n = sizeof(a)/sizeof(a[0]);
    
    cout<<(ls.numOfIncSubseq(a, n));
    
    return 0;
}
2

Java程序查找增加时间最长的子序列

import java.util.*;

class Longestsubseq{

    static int numOfIncSubseq(int[] a, int n){
    
        int[] len = new int[n];
        int[] cnt = new int[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[j]){
        
                    if(len[j]+1 > len[i]){
                        len[i] = len[j]+1;
                        cnt[i] = cnt[j];
                    }
        
                    else if(len[j]+1 == len[i]){
                        cnt[i] += cnt[j];
                    }
                }
        
                lis = Math.max(lis, len[i]);
            }
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            if(len[i] == lis)ans += cnt[i];
        }
        
        return ans;
    }
    
    public static void main (String[] args){
        int[] a = {1,2,5,4,7};
        int n = a.length;
        
        System.out.println(numOfIncSubseq(a, n));
    }
}
2

复杂度分析

时间复杂度

O(n * n) 其中n是给定数组a []中元素的数量。 时间复杂度与找到最长的递增子序列所需的时间相同。

空间复杂度

O(N) 因为我们使用了额外的n个空间。 我们使用了len []数组,该数组存储以ith元素结尾的最长的递增子序列。