최장 증가 부분 수열은 한 항목이 이전 항목보다 큰 부분 수열입니다. 여기서 우리는 정수 집합에서 가장 긴 증가 부분 시퀀스 길이를 찾으려고 노력할 것입니다.
입력 및 출력
Input: A set of integers. {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} Output: The length of longest increasing subsequence. Here it is 6. The subsequence is 0, 2, 6, 9, 13, 15.
알고리즘
longestSubSeq(subarray, n)
입력 - 하위 배열 및 하위 배열의 크기입니다.
출력 - 가장 긴 증가하는 하위 시퀀스 길이입니다.
Begin define array length of size n initially set 0 to all entries of length for i := 1 to n-1, do for j := 0 to i-1, do if subarray[j] < subarray[i] and length[j] > length[i], then length[i] := length[j] done increase length[i] by 1 done lis := 0 for i := 0 to n-1, do lis := maximum of lis and length[i] done return lis End
예시
#include <iostream> using namespace std; int longestSubSeq(int subArr[], int n) { int length[n] = { 0 }; //set all length to 0 length[0] = 1; //subsequence ending with subArr[0] is 1 for (int i = 1; i < n; i++) { //ignore first character, second to all for (int j = 0; j < i; j++) { //subsequence ends with subArr[j] if (subArr[j] < subArr[i] && length[j] > length[i]) length[i] = length[j]; } length[i]++; //add arr[i] } int lis = 0; for (int i = 0; i<n; i++) // find longest increasing subsequence lis = max(lis, length[i]); return lis; } int main() { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; int n = 16 cout << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n); return 0; }
출력
Length of Longest Increasing Subsequence is: 6