인접 항목 간의 차이가 XNUMX 인 가장 긴 하위 시퀀스


난이도 쉽게
자주 묻는 질문 아마존 아 발라 라 팩트 셋 Fourkites Microsoft
배열 동적 프로그래밍 LIS

“인접 간의 차이가 XNUMX이되는 가장 긴 하위 시퀀스”문제는 정수 정렬. 이제 인접한 요소의 차이가 1이되도록 가장 긴 하위 시퀀스의 길이를 찾아야합니다.

인접 항목 간의 차이가 XNUMX 인 가장 긴 하위 시퀀스

1 2 3 4 7 5 9 4
6

설명

우리가 볼 수 있듯이 조건을 따르는 두 개의 하위 시퀀스가 ​​있습니다. 이들은 {1, 2, 3, 4, 5, 4}이고 다른 하나는 {7, 8}입니다. 따라서 가장 긴 하위 시퀀스가 ​​첫 번째 시퀀스입니다. 따라서 답은 6입니다.

인접 항목 간의 차이가 XNUMX이되도록 가장 긴 하위 시퀀스에 대한 접근 방식

순진한 접근 방식은 이러한 가능한 하위 시퀀스를 생성하는 것입니다. 그러나 우리는 하위 시퀀스 생성이 시간이 많이 걸리는 작업이라는 것을 알고 있습니다. 재귀가 필요하고 시간이 기하 급수적으로 복잡하기 때문입니다. 따라서 문제를 해결하려면 더 나은 접근 방식이 필요합니다. 더 나은 접근 방식은 동적 프로그래밍. 문제는 가장 긴 증가 하위 시퀀스의 문제와 유사하기 때문입니다. 이 문제에서 우리는 인접 요소가 1의 차이를 가져야하는 가장 긴 하위 시퀀스를 찾아야합니다. 따라서 문제를 해결하기 위해 입력 배열의 요소를 탐색하기 시작합니다.

횡단하기 전에 첫 번째 요소 인 기본 케이스를 설정합니다. 항상 길이 1의 하위 시퀀스를 만들 수 있습니다. 단일 요소를 선택하면. 이제 앞으로 나아가면서 우리는 현재 요소와 절대 차이가 1 인 요소를 어떻게 든 찾는 지 역방향으로 계속 확인합니다. 그런 다음 다른 요소를 마지막 요소로 사용하는 하위 시퀀스에 현재 요소를 추가 할 수 있습니다. 그리고 그러한 요소를 찾으면 현재 요소에서 끝나는 하위 시퀀스의 최대 길이를 계속 업데이트합니다. 그리고이 모든 값을 계산 한 후이 모든 값의 최대 값을 찾습니다. 그것이 우리 문제에 대한 답입니다.

암호

인접 항목 간의 차이가 XNUMX이되는 가장 긴 하위 시퀀스에 대한 C ++ 코드

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

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

인접 항목 간의 차이가 XNUMX이되도록 가장 긴 하위 시퀀스에 대한 Java 코드

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

복잡성 분석

시간 복잡성

O (N ^ 2), 두 개의 루프가 있었기 때문입니다. 하나는 단순히 모든 요소를 ​​횡단하고 다른 하나는 횡단 된 모든 요소를 ​​횡단합니다. 따라서 알고리즘의 시간 복잡도는 다항식이됩니다.

공간 복잡성

의 위에), 지금까지 탐색 한 모든 요소에 대한 결과를 저장해야했기 때문입니다. 따라서 공간 복잡성은 선형입니다.