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

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 시트릭스 코드네이션 Facebook 구글 Microsoft 삼성 조호 (Zoho)
이진 검색 동적 프로그래밍 LIS조회수 90

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

우리는 정렬 정렬되지 않은 정수의 가장 길고 증가하는 하위 시퀀스를 찾아야합니다.

  • 하위 시퀀스는 연속적 일 필요는 없습니다.
  • 하위 시퀀스가 ​​증가합니다.

몇 가지 예를 통해 더 잘 이해합시다.

입력

[9, 2, 5, 3, 7, 10, 8]

산출

4

설명

가장 오래 증가하는 하위 시퀀스는 [2,3,7,10]입니다.

접근법 1 : 브 루트 포스

이 접근 방식에는 가능한 모든 하위 집합을 조사하고 본질적으로 증가하는 가장 긴 하위 시퀀스를 찾는 것이 포함됩니다.

이제 배열에서 i 번째 정수를 방문 할 때마다 두 가지 경우가있을 수 있습니다.

  • 하위 시퀀스에 포함될 수 있습니다. 즉 이전 요소보다 큽니다.
  • 이전 요소보다 작고 하위 시퀀스에 포함될 수 없습니다.

그러나 특정 위치에 요소를 포함하든 없든 해당 지점까지 특정 길이의 증가하는 하위 시퀀스가 ​​존재하고 해당 시점까지 발생한 최대 길이를 반환 할 수 있습니다. 코드 스 니펫 (Java 및 C ++에서)으로 더 잘 이해합시다.

가장 긴 하위 시퀀스 증가를위한 Java 프로그램

class Solution 
{
    public int helper(int[] nums,int prev,int cur)
    {
        if(cur==nums.length)
            return 0;
        int on_include=0;
        //If the element at current index is greater than 
        //previous element we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(Math.max(on_include,on_ignore));
    }
    public int lengthOfLIS(int[] nums) 
    {
        int max=helper(nums,Integer.MIN_VALUE,0);
        return max;
    }
}

가장 오래 증가하는 하위 시퀀스를위한 C ++ 프로그램

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int helper(vector<int> nums,int prev,int cur)
    {
        if(cur==nums.size())
            return 0;
        int on_include=0;
        //If we are greater than previous length we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(max(on_include,on_ignore));
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
     int max=helper(nums,-1,0);
        return max;    
    }
};

복잡성 분석

시간 복잡성

O (n ^ 2) 여기서 N은 배열의 크기입니다. 여기서 우리는 O (N * N) 시간 복잡성을 유발하는 두 개의 for 루프를 실행합니다.

공간 복잡성

O (1) 상수 공간 c0mplexity로 이끄는 몇 가지 변수를 사용하기 때문입니다.

접근법 2 : 동적 프로그래밍

[9, 2, 5, 3, 7, 10, 8, 7]에 대해 가장 오래 증가하는 하위 시퀀스를 찾아 보겠습니다.

  • 정수 배열 크기의 배열을 만들어 보겠습니다.
  • 각 요소는 하나 이상의 길이의 하위 시퀀스입니다. 즉, 숫자 자체가 XNUMX로 배열을 초기화합니다.
    1 1 1 1 1 1 1 1
  • i 번째 위치마다 앞의 j 번째 위치를 봅니다.
  • 만약 a [j]
  • i = 2의 경우 i = 0과 i = 1을 통해 동일하게 찾습니다. 작업 후 수정 된 배열을 살펴 보겠습니다.
    1 1 최대 (j + 1, i)

    (2)

    1 1 1 1 1
  • 모든 비교 후 최종 배열은 다음과 같이 볼 수 있습니다.
    1 1 2 2 3 4 4 3
  • 모든 숫자의 최대 값을 구하면 최대 하위 시퀀스의 길이가 4 인 것을 알 수 있습니다. 코드로 이것을 더 잘 이해합시다.

가장 긴 하위 시퀀스 증가를위한 Java 프로그램

class Solution 
{
    public int lengthOfLIS(int[] nums) 
    {
        int ans[]=new int[nums.length];
        for(int i=0;i<ans.length;i++)
            ans[i]=1;
        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=Math.max(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<ans.length;i++)
        {
            max=Math.max(ans[i],max);
        }
        return max;
    }
}

가장 오래 증가하는 하위 시퀀스를위한 C ++ 프로그램

class Solution 
{
public:
    int cmax(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
    int ans[nums.size()];
    int i,j;
        for(i=0;i<nums.size();i++)
            ans[i]=1;
        for(i=1;i<nums.size();i++)
        {
            for(j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=cmax(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            max=cmax(ans[i],max);
        }
        return max; 
    }
};

복잡성 분석

시간 복잡성

위 솔루션의 시간 복잡도는 O (n ^ 2)입니다.

공간 복잡성

O (n) 왜냐하면 각 인덱스 뒤에 답을 저장하기 위해 배열을 사용하기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »