[알고리즘/C++] 최장증가부분수열구하기

최장증가 부분수열이란 수열이 주어졌을 때, 원소가 차례로 증가하는 부분 원소들을 말한다. 예를 들어 2 6 1 5 7 8 4 9 라는 수열이 있으면 증가하는 부분 배열의 예시들은 다음과 같다. 2 6 1 5 7 8 4 9 2 6 1 5 7 8 4 9 2 6 1 5 7 8 4 9 위의 3가지 예시에서 가장 길이가 긴 케이스는 1번과 2번 케이스로 5의 길이를 가진다. 가장 길이가 긴 케이스를 찾는 알고리즘을 동적 계획법으로 해결해보자. #include using namespace std; typedef vector vi; vi longestIncreasingSubseq(vi arr) { vi leng(arr.size(), 0); //벡터 초기화 for (int k = 0; k < arr.size(); k+..

2023.07.28