새로운 가장 긴 증가하는 부분 수열, LIS

코드 :

#include <iostream>
#include <algorithm>
using namespace std;
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int main() {
    fastio();
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    int cnt = 0;
    
    while (!arr.empty()) {
        int idx = 0;
        while (true) {
            int maximum = -1;
            int maxIdx = -1;
            for (int i = idx; i < n; i++) {
                if (maximum < arr[i]) {
                    maximum = arr[i];
                    maxIdx = i;
                }
            }
            if (maxIdx == -1) break;
            arr.erase(arr.begin() + maxIdx);
            idx = maxIdx;
            n--;
        }
        cnt++;
    }
    
    cout << cnt;
    return 0;
}
 

---

해설 : 

최대 값의 인덱스를 구합니다

1. 주어진 배열에서 최대 값의 인덱스를 구합니다.

---

2. 최대 값을 제거합니다.

---

3. 2에서 구한 최대 값 이후의 최대 값을 구하여 삭제합니다.

---

4. 2와 3을 더이상 수정되지 않을 때 까지 반복합니다.

 

---

5. 벡터가 빌 때 까지 반복하고, 1~4번을 반복한 회수를 출력합니다. 

---

예제와 함께 이해하기 :

arr	10	9	20	30	50	50	41	42	60
delete									1

 

arr	10	9	20	30	50	50	41	42	60
delete						2		2	1

 

arr	10	9	20	30	50	50	41	42	60
delete					3	2	3	2	1

 

arr	10	9	20	30	50	50	41	42	60
delete				4	3	2	3	2	1

 

arr	10	9	20	30	50	50	41	42	60
delete			5	4	3	2	3	2	1

 

arr	10	9	20	30	50	50	41	42	60
delete	6	6	5	4	3	2	3	2	1

고로 답이 6이 됩니다.