LIS 문제를 풀기 위해 LOWER BOUND를 사용하였구요.
이진검색 함수를 사용해서 logn의 탐색을 보장 받았습니다.
배열의 크기만큼 arr_max를 채우고 있기 때문에 최종적으로
nlogn의 시간복잡도를 갖는다고 생각하는데도 불구하고 시간초과가 나옵니다. ㅠ
어디서 시간을 잡아먹고 있는지 전혀 알수가 없습니다.
고수님들 조언 좀 부탁드립니다.

~~~ c++
#include
#include
#include
#include
using namespace std;
//LIS
const int MAX_LENGTH = 500;
int arr_max[MAX_LENGTH];
int result[MAX_LENGTH];

int binarySearch(int first, int last, int value)
{
if (first > last)
return 0;

int mid = (first + last) / 2;

if (arr_max[mid-1] < value && arr_max[mid] > value)
    return mid;

else if (arr_max[mid - 1] > value)
    return binarySearch(0, mid, value);

else 
    return binarySearch(mid + 1, last, value);

}

int calculate_maxSize(int arr[], int length)
{
int index = 0;
int size = 0;
arr_max[index] = arr[0];
for (int i = 1; i < length; i++)
{
if (arr_max[index] < arr[i])
arr_max[++index] = arr[i];

    else
    {
        int temp = binarySearch(0, index, arr[i]);
        arr_max[temp] = arr[i];
    }
}

while (arr_max[size] != 0)
    size++;

return size;

}

int main()
{
int caseNum;
int arrSize = 0;
int arr[MAX_LENGTH];

cin >> caseNum;
for (int i = 0; i < caseNum; i++)
{
    memset(arr_max, 0, sizeof(int)*arrSize);
    cin >> arrSize;

    for (int j = 0; j < arrSize; j++)
        cin >> arr[j];

    cout << calculate_maxSize(arr, arrSize) << endl;
}
return 0;

}
}
~~~