LIS(최장 증가 부분 수열)

int LIS() { 
v.push_back(-1000000001);

 

for (int i = 0; i < n; ++i) {
if (arr[i] > v.back()) {
v.push_back(arr[i]);
cnt++;
}
else {
deque ::iterator itr = lower_bound(v.begin(), v.end(), arr[i]);
*itr = arr[i];
}
}

return cnt;
}

 

*주의 : 배열의 순서는 고려하지 않음