범위가 커졌을 때의 최대 긴 증가수열

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int number[1000001];
vector<int> arr;

int lowerbound(int src, int dest, int found)
{
int middle;
while (src - dest > 0)
{
middle = (src + dest) / 2;
if (number[middle] < found)
src = middle + 1;
else
dest = middle;
}

return dest + 1;
}

int main(void)
{
arr.push_back(-1);
int ans=0;

int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> number[i];
}

for (int i = 0; i < n; i++)
{
if (arr.back() < number[i])
{
arr.push_back(number[i]);
ans++;
}
else
{
//auto daiti = lower_bound(arr.begin(),
// arr.end(), number[i]);
int daiti = lowerbound(0, arr.size(), number[i]);
daiti = number[i];
}
}

cout << ans;

return 0;
}

 

실제 정답이 되는 부분은 주석처리한 부분.

lower_bound를 실제로 구현한 부분은 맨 위.

 

만일 auto로 접근할 경우, 

auto형으로 감싼 daiti를 통해 값을 바꾼다.

daiti는 std::vector<int>::iterator daiti의 반복자 형태로 반환된다.

따라서 바로 *daiti를 통해 값의 변환이 가능하다.

이때ㅡ *daiti는, daiti가 가리키는 원소(또는 객체)를 반환한다.

 

만일 이를 쓰지 않고 그냥 int로 할 경우,

vector[daiti]=number[i]로 값의 변환이 가능하다.