가장 긴 Bitonic 하위 시퀀스

난이도 하드
자주 묻는 질문 코드네이션 드 쇼 구글 JP 모건 Microsoft
배열 동적 프로그래밍조회수 73

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

당신이 정렬 of 정수, 문제 설명은 가장 긴 비트 시퀀스를 찾아야합니다. 배열의 비 토닉 시퀀스는 먼저 증가한 다음 감소하는 시퀀스로 간주됩니다.

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

설명

1 4 76 78 54 32 23 (먼저 78까지 증가한 다음 23까지 감소합니다.

가장 긴 Bitonic 하위 시퀀스

 

암호알고리즘

  1. 배열 선언 incrementSeq [] 주어진 배열 길이의 길이와 같은 크기입니다.
  2. 모든 인덱스 요소를 생성 된 배열 incrementSeq []의 1로 초기화합니다.
  3. 왼쪽에서 오른쪽으로 incrementSeq []에 저장하여 가장 긴 증가 하위 시퀀스를 찾으십시오.
  4. 배열 선언 decreasingSeq [] 주어진 배열의 길이와 같은 크기.
  5. 오른쪽에서 왼쪽으로 이동하고 decreasingSeq []에 저장하여 가장 긴 감소하는 하위 시퀀스를 찾습니다.
  6. maxOutput이라는 변수를 incrementSeq [0] + decreasingSeq [0] – 1로 초기화하십시오.
  7. 최대 값 알아보기 incrementSeq [i] + decreasingSeq [i] – 1 maxOutput에 저장합니다.
  8. 반환 최대 출력.

설명

크기 n의 입력 배열은 양의 정수로 구성됩니다. 주어진 배열의 가장 긴 비 토닉 시퀀스를 찾아야합니다. 비 토닉 시퀀스는 먼저 증가하는 시퀀스로 정의 할 수 있으며, 이는 시퀀스의 숫자가 먼저 증가 함을 의미합니다. 그런 다음 시퀀스가 ​​끝날 때까지 숫자가 감소합니다. 가장 긴 비 토닉 시퀀스의 길이를 결정해야합니다.

먼저 솔루션을 두 부분으로 분리하십시오. 두 개의 배열을 선언합니다. 첫 번째 배열은 incrementSeq 정렬. 가장 긴 증가 시퀀스는 증가 시퀀스에서 숫자가 첫 번째 여야하는 시퀀스입니다. 그래서 우리는 중첩 된 루프에서 배열을 순회 할 것입니다. 증가하는 하위 시퀀스를 계속 찾으십시오. 그런 다음 현재 요소가 다음 요소보다 작은 지 확인해야합니다. 또한 incrementSeq의 현재 요소는 incrementSeq []의 다음 요소보다 작습니다. 참이면 요소를 incrementSeq [j] + 1로 저장하십시오. 이것은 배열을 이미 1로 초기화했기 때문에 더해집니다.

둘째, 배열을 선언하고 decreasingSeq []. 이 decreasingSeq []에서 배열의 오른쪽에서 왼쪽으로 중첩 된 루프 방식으로 배열을 순회합니다. 현재 요소가 다음 요소보다 큰지 확인합니다. 우리는 오른쪽에서 왼쪽으로 횡단하고 있기 때문입니다. 그런 다음 decreasingSeq [i]를 decreasingSeq [j] +1로 업데이트합니다. 코드의 마지막 단계에서 maxOutput에 저장된 최대 incrementSeq [i] + decreasingSeq [i] – 1을 찾아야합니다.

암호

가장 긴 Bitonic 하위 시퀀스에 대한 C ++ 코드

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

가장 긴 Bitonic 하위 시퀀스에 대한 Java 코드

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

복잡성 분석

시간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. 알고리즘이 다항식 시간에 실행되도록하는 중첩 루프를 사용했기 때문입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 크기가 입력 배열에 따라 달라지는 두 개의 추가 배열을 사용했기 때문입니다. 공간 복잡성은 선형입니다.

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