Нахождение самой длинной возрастающей подпоследовательности в круглом столе чисел

Я недавно работал над следующей проблемой.
http://www.codechef.com/problems/D2

Шеф-повар планирует фуршет для инаугурации DirectiPlex, и все приглашены. По пути каждый гость берет лист бумаги, содержащий случайное число (это число может повторяться). Затем гости садятся за круглый стол со своими друзьями.
Теперь шеф-повар решает, что он хотел бы сыграть в игру. Он просит вас выбрать случайного человека из вашего стола и попросить его прочитать вслух их число. Затем, двигаясь по часовой стрелке вокруг стола, каждый человек зачитает свой номер. Цель состоит в том, чтобы найти тот набор чисел, который образует возрастающую подпоследовательность. Все люди, владеющие этими номерами, получат право на счастливую ничью! Один из разработчиков программного обеспечения очень взволнован этой перспективой и хочет максимизировать количество людей, которые имеют право на счастливую ничью. Таким образом, он решает написать программу, которая решает, кто должен сначала прочитать их число, чтобы максимизировать количество людей, которые имеют право на счастливую ничью. Можете ли вы победить его?

вход

Первая строка содержит t, количество тестовых случаев (около 15). затем t контрольные примеры следуют. Каждый тестовый набор состоит из двух строк:

1. Первая строка содержит число NКоличество гостей, приглашенных на вечеринку.
2. Вторая строка содержит N чисел a1, a2, ..., an разделены пробелами, которые представляют собой числа, написанные на листах бумаги по часовой стрелке.

Выход

Для каждого теста выведите строку, содержащую одно число, которое является максимальным количеством гостей, которые могут иметь право участвовать в розыгрыше.

Ограничения

1 ≤ N ≤ 10000
Вы можете предположить, что каждый номер числа на листе бумаги; ai генерируется случайным образом, то есть может быть с равной вероятностью любым числом из интервала [0,U], где U некоторая верхняя граница (1 ≤ U ≤ 106).

пример

Входные данные:

3
2
0 0
3
3 2 1
6
4 8 6 1 5 2

Выход:

1
2
4

При проверке решений я нашел этот код:

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

#define LIMIT 37

using namespace std;

struct node {
int val;
int index;
};

int N;

int binary(int number, vector<int>& ans) {
int start = 0;
int n = ans.size();
int end = n - 1;
int mid;
if (start == end)
return 0;
while (start != end) {
mid = (start + end) / 2;
if (ans[mid] == number)
break;
if (ans[mid] > number)
end = mid;
else
start = mid + 1;
}
mid = (start + end) / 2;
return mid;
}

void display(vector<int>& list) {
cout << endl;
for (int i = 0; i < list.size(); i++)
cout << list[i] << " ";
cout << endl;
}

int maxsubsequence(vector<int>& list) {
vector<int> ans;
int N = list.size();
ans.push_back(list[0]);
int i;
// display(list);
for (i = 1; i < N; i++) {
int index = binary(list[i], ans);
/*if(index+1<ans.size())
continue;*/
if (list[i] < ans[index])
ans[index] = list[i];
if (list[i] > ans[index])
ans.push_back(list[i]);
// display(ans);
}
return ans.size();
}

int compute(int index, int* g) {
vector<int> list;
list.push_back(g[index]);
int itr = (index + 1) % N;
while (itr != index) {
list.push_back(g[itr]);
itr = (itr + 1) % N;
}
return maxsubsequence(list);
}

int solve(int* g, vector<node> list) {
int i;
int ret = 1;
for (i = 0; i < min(LIMIT, (int)list.size()); i++) {
// cout<<list[i].index<<endl;
ret = max(ret, compute(list[i].index, g));
}
return ret;
}

bool cmp(const node& o1, const node& o2)
{ return (o1.val < o2.val); }

int g[10001];

int main() {
int t;
cin >> t;
while (t--) {
cin >> N;
vector<node> list;
int i;
for (i = 0; i < N; i++) {
node temp;
cin >> g[i];
temp.val = g[i];
temp.index = i;
list.push_back(temp);
}
sort(list.begin(), list.end(), cmp);
cout << solve(g, list) << endl;
}
return 0;
}

Может кто-то объяснить это мне. Я хорошо знаю, как вычислить LIS в nlog (n).
Что я не могу понять, так это часть:

int ret = 1;
for (i = 0; i < min(LIMIT, (int)list.size()); i++) {
// cout<<list[i].index<<endl;
ret = max(ret, compute(list[i].index, g));
}

и причина сортировки

sort(list.begin(),list.end(),cmp);