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

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

an array A consisting of N integers.
M queries (Li, Ri)
for each query we wants to find the length of the longest increasing subsequence in
array A[Li], A[Li + 1], ..., A[Ri].

Я реализовал поиск подпоследовательности, используя подход dp

// mind the REPN, LLD, these are macros I use for programming
// LLD = long long int
// REPN(i, a, b) = for (int i = a; i < b; ++i)
LLD a[n], dp[n];
REPN(i, 0, n)
{
scanf("%lld", &a[i]);
dp[i] = 1;
}
REPN(i, 1, n)
{
REPN(j, 0, i)
{
if(a[i] > a[j])
dp[i] = std::max(dp[j] + 1, dp[i]);
}
}

Например:

Array: 1 3 8 9 7 2 4 5 10 6
dplis: 1 2 3 4 3 1 3 4 5  5
max: 5

Но если бы это было для диапазона Li=2 & Ri=9

Затем:

Array: 3 8 9 7 2 4 5 10
dplis: 1 2 3 2 1 2 3 4
max: 4

Как я могу определить максимальную самую длинную увеличивающуюся подпоследовательность в подмассиве?

PS: Я не хочу пересчитывать весь массив dplis, я хочу использовать исходный, потому что слишком много вычислений убьет цель вопроса.

Один из подходов заключался в создании полного 2D-массива DP, который состоит из подпоследовательности из положения i, где диапазон i составляет от 0 до n, но во многих случаях он не срабатывает из-за TLE(Превышен лимит времени)

REPN(k,0,n) {
REPN(i,k+1,n) {
REPN(j,k,i) {
if(a[i]>a[j]) dp[k][i]=std::max(dp[k][j]+1, dp[k][i]);
}
}
}

REPN(i,0,q) {
read(l); read(r);

LLD max=-1;
REPN(i,0,r) {
if(max<dp[l-1][i]) max=dp[l-1][i];
}

printf("%lld\n", max);
}

Если у вас есть какая-либо новая логика / реализация, я с удовольствием изучу ее всесторонне. Приветствия.