LIS(최장 증가 부분 수열) - TECHCODEVIEW.COM

배열이 주어지면 도착[] 크기의 N , 작업은 가장 긴 증가 부분 수열(LIS)의 길이, 즉 부분 수열의 요소가 오름차순으로 정렬되는 가능한 가장 긴 부분 수열을 찾는 것입니다.

가장 긴 증가 부분 수열

예:

입력: 도착[] = {3, 10, 2, 1, 20}
산출: 삼
설명: 가장 긴 증가 부분 수열은 3, 10, 20입니다.

입력: 도착[] = {50, 3, 10, 7, 40, 80}
산출: 4
설명: 가장 긴 증가 부분 수열은 {3, 7, 40, 80}입니다.

글꼴 김프

입력: 도착[] = {30, 20, 10}
산출: 1
설명: 가장 길게 증가하는 부분 수열은 {30}, {20} 및 (10)입니다.

입력: 도착[] = {10, 20, 35, 80}
산출: 4
설명: 전체 배열이 정렬되었습니다.

다음을 사용하여 가장 긴 증가 수열 재귀 :

입력 배열을 왼쪽에서 오른쪽으로 탐색하고 모든 요소 arr[i]로 끝나는 LIS(Longest Going Subsequence)의 길이를 찾는 아이디어입니다. arr[i]에 대해 구한 길이를 L[i]로 둡니다. 마지막에는 모든 L[i] 값의 최대값을 반환합니다. 이제 질문이 생깁니다. L[i]를 어떻게 계산합니까? 이를 위해 우리는 재귀를 사용합니다. arr[i] 왼쪽에 있는 모든 작은 요소를 고려하고 왼쪽에 있는 모든 작은 요소에 대한 LIS 값을 재귀적으로 계산하고 모든 것의 최대값을 취하여 1을 더합니다. 요소 왼쪽에 더 작은 요소가 없으면 1을 반환합니다.

허락하다 엘(i) 인덱스로 끝나는 LIS의 길이 나 arr[i]는 LIS의 마지막 요소입니다. 그러면 L(i)는 다음과 같이 재귀적으로 쓸 수 있습니다.
인스턴스화된 자바

L(i) = 1 + max(L(j) ) 여기서 0
L(i) = 1(해당 j가 존재하지 않는 경우)
공식적으로 LIS의 길이는 인덱스로 끝납니다. 나 는 일부 인덱스에서 끝나는 모든 LIS의 최대 길이보다 1 더 큽니다. 제이 그렇게 도착[j] 어디 제이 .

위의 반복관계는 다음과 같다는 것을 알 수 있다. 최적의 하부구조 재산.

삽화:
자바 유효한 식별자

더 나은 이해를 위해 아래 그림을 따르십시오.

arr[] = {3, 10, 2, 11}을 고려하세요.

L(i): 'i' 위치에서 끝나는 하위 배열의 LIS를 나타냅니다.

재귀 트리

위의 아이디어를 구현하려면 아래에 언급된 단계를 따르세요.

재귀 함수를 만듭니다.
각 재귀 호출에 대해 나는 = 1 현재 위치로 이동하여 다음을 수행합니다.
이전 수열이 다음 위치에서 끝났다면 현재 위치에서 끝나는 가장 긴 증가 부분 수열의 가능한 길이를 구합니다. 나 .
이에 따라 가능한 최대 길이를 업데이트하십시오.
모든 지수에 대해 이를 반복하고 답을 찾습니다.
다음은 재귀 접근 방식의 구현입니다.
사이라 바누 배우
C++// A Naive C++ recursive implementation // of LIS problem #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end // with an element before arr[n-1] max_ref // is used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of // LIS ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with // arr[0], arr[1] ... arr[n-2]. If // arr[i-1] is smaller than arr[n-1], // and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here를 // 전체 최대값과 비교합니다. // 필요한 경우 전체 최대값을 업데이트합니다(*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending // with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its // result in max _lis(arr, n, &max); // Returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << 'Length of lis is ' << lis(arr, n); return 0; }>씨// A Naive C recursive implementation // of LIS problem #include #include // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] // needs to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here를 전체 // 최대 값과 비교합니다. 필요한 경우 전체 최대값을 업데이트합니다(*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf('Length of lis is %d', lis(arr, n)); return 0; }>자바// A Naive Java Program for LIS Implementation import java.io.*; import java.util.*; class LIS { // Stores the LIS static int max_ref; // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int _lis(int arr[], int n) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here를 전체 최대값과 비교합니다. 그리고 // 필요한 경우 전체 최대값을 업데이트합니다.< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int arr[], int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void main(String args[]) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; // Function call System.out.println('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Rajat Mishra>파이썬# A naive Python implementation of LIS problem # Global variable to store the maximum global maximum # To make use of recursive calls, this function must return # two things: # 1) Length of LIS ending with element arr[n-1]. We use # max_ending_here for this purpose # 2) Overall maximum as the LIS may end with an element # before arr[n-1] max_ref is used this purpose. # The value of LIS of full array of size n is stored in # *max_ref which is our final result def _lis(arr, n): # To allow the access of global variable global maximum # Base Case if n == 1: return 1 # maxEndingHere is the length of LIS ending with arr[n-1] maxEndingHere = 1 # Recursively get all LIS ending with # arr[0], arr[1]..arr[n-2] # If arr[i-1] is smaller than arr[n-1], and # max ending with arr[n-1] needs to be updated, # then update it for i in range(1, n): res = _lis(arr, i) if arr[i-1] < arr[n-1] and res+1>maxEndingHere: maxEndingHere = res + 1 # maxEndingHere를 전체 최대값과 비교합니다. 그리고 # 필요한 경우 전체 최대값을 업데이트합니다 maximum = max(maximum, maxEndingHere) return maxEndingHere def lis(arr): # 전역 변수에 대한 액세스를 허용하려면 global maximum # arr의 길이 n = len(arr) # Maximum 변수는 결과를 보유합니다. maximum = 1 # _lis() 함수는 결과를 maximum에 저장합니다. _lis(arr, n) return maximum # 위 함수를 테스트하기 위한 드라이버 프로그램 if __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # 함수 호출 print('Length of lis is', lis(arr)) # 이 코드는 NIKHIL KUMAR SINGH가 기여했습니다>씨#using System; // A Naive C# Program for LIS Implementation class LIS { // Stores the LIS static int max_ref; // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int _lis(int[] arr, int n) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here를 전체 최대값과 비교하고 // 필요한 경우 전체 최대값을 업데이트합니다(max_ref< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int[] arr, int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void Main() { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; // Function call Console.Write('Length of lis is ' + lis(arr, n) + ' '); } }>자바스크립트>
산출
Length of lis is 5>

시간 복잡도: 오(2^N) 위의 재귀 트리 다이어그램에서 설명한 것처럼 하위 문제가 겹치는 경우가 있기 때문에 이 재귀 접근 방식의 시간 복잡도는 기하급수적입니다.
보조 공간: 오(1). 내부 스택 공간과 별도로 값을 저장하는 데 외부 공간이 사용되지 않습니다.

다음을 사용하여 가장 긴 증가 부분 수열 메모 :

주의 깊게 살펴보면 위의 재귀 솔루션도 다음을 따른다는 것을 알 수 있습니다. 중복되는 하위 문제 즉, 동일한 하위 구조가 다른 재귀 호출 경로에서 계속해서 해결됩니다. 메모이제이션 접근 방식을 사용하면 이를 방지할 수 있습니다.

두 가지 매개변수를 사용하여 각 상태를 고유하게 식별할 수 있음을 확인할 수 있습니다.

현재 지수 (LIS의 마지막 인덱스를 나타냄) 및
이전 색인 (뒤에 있는 이전 LIS의 종료 인덱스를 나타냅니다. 도착[i] 연결 중입니다.)
아래는 위의 접근 방식을 구현한 것입니다.
초기 무커
C++// C++ code of memoization approach for LIS #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int f(int idx, int prev_idx, int n, int a[], vector>& dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = INT_MIN; if (prev_idx == -1 || a[idx]> a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx][prev_idx + 1] = max(take, notTake); } // // 가장 긴 증가 부분 수열의 길이를 찾는 함수 int maximumSubsequence(int n, int a[]) { 벡터> dp(n + 1, 벡터 (n + 1, -1)); f(0, -1, n, a, dp)를 반환합니다. } // 위 테스트를 위한 드라이버 프로그램 function int main() { int a[] = { 3, 10, 2, 1, 20 }; int n = sizeof(a) / sizeof(a[0]); // 함수 호출 cout<< 'Length of lis is ' << longestSubsequence(n, a); return 0; }>자바// A Memoization Java Program for LIS Implementation import java.lang.*; import java.util.Arrays; class LIS { // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int f(int idx, int prev_idx, int n, int a[], int[][] dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = Integer.MIN_VALUE; if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx][prev_idx + 1] = Math.max(take, notTake); } // _lis()에 대한 래퍼 함수 static int lis(int arr[], int n) { // _lis() 함수는 결과를 max int에 저장합니다. dp[][] = new int[n + 1][ n + 1]; for (int row[] : dp) Arrays.fill(row, -1); f(0, -1, n, arr, dp)를 반환합니다. } // 위 함수를 테스트하기 위한 드라이버 프로그램 public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 }; int n = a.길이; // 함수 호출 System.out.println('lis의 길이는 ' + lis(a, n)); } } // 이 코드는 Sanskar가 제공한 것입니다.>파이썬# A Naive Python recursive implementation # of LIS problem import sys # To make use of recursive calls, this # function must return two things: # 1) Length of LIS ending with element arr[n-1]. # We use max_ending_here for this purpose # 2) Overall maximum as the LIS may end with # an element before arr[n-1] max_ref is # used this purpose. # The value of LIS of full array of size n # is stored in *max_ref which is our final result def f(idx, prev_idx, n, a, dp): if (idx == n): return 0 if (dp[idx][prev_idx + 1] != -1): return dp[idx][prev_idx + 1] notTake = 0 + f(idx + 1, prev_idx, n, a, dp) take = -sys.maxsize - 1 if (prev_idx == -1 or a[idx]>a[prev_idx]): take = 1 + f(idx + 1, idx, n, a, dp) dp[idx][prev_idx + 1] = max(take, notTake) return dp[idx][prev_idx + 1] # 가장 길게 증가하는 부분 수열의 길이를 찾는 함수. def maximumSubsequence(n, a): dp = [[-1 for i in range(n + 1)]for j in range(n + 1)] return f(0, -1, n, a, dp) # 드라이버 위 함수를 테스트하는 프로그램 if __name__ == '__main__': a = [3, 10, 2, 1, 20] n = len(a) # 함수 호출 print('Length of lis is',longestSubsequence( n, a)) # 이 코드는 shinjanpatra가 제공한 것입니다.>씨#// C# approach to implementation the memoization approach using System; class GFG { // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result public static int INT_MIN = -2147483648; public static int f(int idx, int prev_idx, int n, int[] a, int[, ] dp) { if (idx == n) { return 0; } if (dp[idx, prev_idx + 1] != -1) { return dp[idx, prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = INT_MIN; if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx, prev_idx + 1] = Math.Max(take, notTake); } // 가장 길게 증가하는 부분 수열의 길이를 찾는 함수입니다. public static intlongSubsequence(int n, int[] a) { int[, ] dp = new int[n + 1, n + 1]; for (int i = 0; i< n + 1; i++) { for (int j = 0; j < n + 1; j++) { dp[i, j] = -1; } } return f(0, -1, n, a, dp); } // Driver code static void Main() { int[] a = { 3, 10, 2, 1, 20 }; int n = a.Length; Console.WriteLine('Length of lis is ' + longestSubsequence(n, a)); } } // The code is contributed by Nidhi goel.>자바스크립트/* A Naive Javascript recursive implementation of LIS problem */ /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ function f(idx, prev_idx, n, a, dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } var notTake = 0 + f(idx + 1, prev_idx, n, a, dp); var take = Number.MIN_VALUE; if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); } return (dp[idx][prev_idx + 1] = Math.max(take, notTake)); } // 가장 길게 증가하는 부분 수열의 길이를 찾는 함수입니다. function maximumSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1)); f(0, -1, n, a, dp)를 반환합니다. } /* 위 기능을 테스트하기 위한 드라이버 프로그램 */ var a = [3, 10, 2, 1, 20]; var n = 5; console.log('lis의 길이는 ' + maximumSubsequence(n, a)); // 이 코드는 satwiksuman이 제공한 것입니다.>
산출
Length of lis is 3>

시간 복잡도: 에²)
보조 공간: 에²)

다음을 사용하여 가장 긴 증가 부분 수열 동적 프로그래밍 :

최적의 하위 구조와 중첩되는 하위 문제 속성으로 인해 동적 프로그래밍을 활용하여 문제를 해결할 수도 있습니다. 메모 대신 중첩 루프를 사용하여 재귀 관계를 구현할 수 있습니다.

외부 루프는 다음에서 실행됩니다. 나는 = 1에서 N까지 내부 루프는 다음에서 실행됩니다. j = 0 ~ i 문제를 해결하기 위해 반복 관계를 사용합니다.

다음은 위의 접근 방식을 구현한 것입니다.
C++// Dynamic Programming C++ implementation // of LIS problem #include using namespace std; // lis() returns the length of the longest // increasing subsequence in arr[] of size n int lis(int arr[], int n) { int lis[n]; lis[0] = 1; // Compute optimized LIS values in // bottom up manner for (int i = 1; i < n; i++) { lis[i] = 1; for (int j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; } // Return maximum value in lis[] return *max_element(lis, lis + n); } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf('Length of lis is %d ', lis(arr, n)); return 0; }>자바// Dynamic Programming Java implementation // of LIS problem import java.lang.*; class LIS { // lis() returns the length of the longest // increasing subsequence in arr[] of size n static int lis(int arr[], int n) { int lis[] = new int[n]; int i, j, max = 0; // Initialize LIS values for all indexes for (i = 0; i < n; i++) lis[i] = 1; // Compute optimized LIS values in // bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; // Pick maximum of all LIS values for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } // Driver code public static void main(String args[]) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; // Function call System.out.println('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Rajat Mishra>파이썬# Dynamic programming Python implementation # of LIS problem # lis returns length of the longest # increasing subsequence in arr of size n def lis(arr): n = len(arr) # Declare the list (array) for LIS and # initialize LIS values for all indexes lis = [1]*n # Compute optimized LIS values in bottom up manner for i in range(1, n): for j in range(0, i): if arr[i]>arr[j] 및 lis[i]< lis[j] + 1: lis[i] = lis[j]+1 # Initialize maximum to 0 to get # the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range(n): maximum = max(maximum, lis[i]) return maximum # Driver program to test above function if __name__ == '__main__': arr = [10, 22, 9, 33, 21, 50, 41, 60] print('Length of lis is', lis(arr)) # This code is contributed by Nikhil Kumar Singh>씨#// Dynamic Programming C# implementation of LIS problem using System; class LIS { // lis() returns the length of the longest increasing // subsequence in arr[] of size n static int lis(int[] arr, int n) { int[] lis = new int[n]; int i, j, max = 0; // Initialize LIS values for all indexes for (i = 0; i < n; i++) lis[i] = 1; // Compute optimized LIS values in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; // Pick maximum of all LIS values for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } // Driver code public static void Main() { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; // Function call Console.WriteLine('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Ryuga>자바스크립트>
산출
Length of lis is 5>

시간 복잡도: 에²) 중첩 루프가 사용됩니다.
보조 공간: O(N) 각 인덱스에 LIS 값을 저장하기 위해 임의의 배열을 사용합니다.

메모: 위 DP(동적 프로그래밍) 솔루션의 시간 복잡도는 O(n^2)이지만 O(N* logN) 솔루션 LIS 문제에 대해 여기서는 O(N log N) 솔루션에 대해 논의하지 않았습니다.
나타내다: 가장 긴 증가 부분 수열 크기(N * logN) 언급된 접근 방식에 대해.