가장 오래 증가하는 하위 시퀀스 수

난이도 중급
자주 묻는 질문 아마존 삼성 조호 (Zoho)
배열 동적 프로그래밍조회수 30

문제 정책

“Number Of Longest Increasing Subsequence”문제는 n 크기의 배열 a []가 주어 졌음을 나타냅니다. 가장 오래 증가하는 하위 시퀀스 수를 인쇄합니다.

가장 오래 증가하는 하위 시퀀스 수핀

예

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

설명 : 가장 오래 증가하는 하위 시퀀스는 위 이미지에서 볼 수 있습니다.

입력 : a [] = {1, 2, 3, 4, 5}

출력 : 1 (1,2,3,4,5는 여기서 가장 긴 하위 시퀀스입니다)

가장 오래 증가하는 하위 시퀀스 수 알고리즘

  1. 초기화 정렬 a [] / 정수 크기 n의 유형.
  2. 수를 찾는 함수를 만듭니다. 가장 오래 증가하는 하위 시퀀스 정수 유형의 배열과 매개 변수의 크기를 허용합니다.
  3. 정수형 len 및 cnt 크기 n의 배열 두 개를 만들고 두 배열의 모든 요소를 ​​1로 초기화합니다. 또한 정수 변수 lis = 1을 초기화합니다.
  4. i를 사용하여 1에서 n-1까지 이동하고 0에서 i-1까지 내부 루프를 만듭니다.
  5. 외부 루프의 현재 인덱스에있는 배열 a []의 요소가 내부 루프의 현재 인덱스에있는 배열 a []의 요소보다 큰지 확인하고, 내부 루프의 현재 인덱스에있는 배열 len []의 값 + 1이 있는지 확인합니다. 루프가 외부 루프의 현재 인덱스에서 배열 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와 같은지 확인하고 ans에있는 cnt의 현재 인덱스에 값을 추가합니다.
  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 공간을 사용했기 때문입니다. 우리는 i 번째 요소에서 끝나는 가장 긴 증가하는 하위 시퀀스를 저장하는 len [] 배열을 사용했습니다.

Translate »
1