Построение самой длинной возрастающей подпоследовательности из стадии 1 вида терпения

Я пытаюсь построить самую длинную последовательность из стадии 1 типа терпения. Это работает в O (n log n). Однако, пытаясь построить самую длинную подпоследовательность из отдельных куч, я не могу придумать что-то более быстрое, чем O (n ^ 2). Алгоритм, который я использую (в C ++), следующий. Если требуется дальнейшее объяснение, я могу сделать дополнительное объяснение, я могу сделать это.

 vector<int> composeLIS(const vector<vector<int>>& piles)
{
vector<int> LIS;
int prev;
for (auto i = v.end()-1; i >= v.begin(); i--)
{
if (i == v.end() - 1)
{
auto j = i[i->size()-1][0];
LIS.push_back(j);
prev = j;
}
else
{
for (auto j = i->begin(); j < i->end(); j++)
{
if (prev > *j)
{
LIS.insert(LIS.begin(),*j);
prev = *j;
break;
}
}
}
}
return LIS;
}

Есть ли способ составить подпоследовательность по сложности лучше, чем O (n ^ 2)?

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]