Как уменьшить сложность времени, чтобы найти самую длинную зигзагообразную последовательность?

Поскольку подпоследовательность не обязательно должна быть смежной, вы не можете сделать это O (n). В худшем случае сложность O (2 ^ n). Тем не менее, я сделал несколько проверок, чтобы отрезать поддеревья как можно скорее.

int maxLenght;

void test(vector<int>& a, int sign, int last, int pos, int currentLenght) {
if (maxLenght < currentLenght) maxLenght = currentLenght;
if (pos >= a.size() || pos >= a.size() + currentLenght - maxLenght) return;
if (last != a[pos] && (last - a[pos] >= 0) != sign)
test(a,!sign,a[pos],pos+1,currentLenght+1);
test(a,sign,last,pos+1,currentLenght);
}

int longestZigZag(vector<int>& a) {
maxLenght = 0;
test(a,0,a[0],1,1);
test(a,!0,a[0],1,1);
return maxLenght;
}

Ты можешь использовать RMQs удалить внутренний цикл for. Когда вы найдете ответ для dp[i][0] а также dp[i][1], сохранить его в двух деревьях RMQ — скажем, RMQ₀ и RMQ₁ — так же, как вы делаете сейчас с двумя рядами dp массив. Итак, когда вы рассчитываете dp[i][0], вы ставите значение dp[i][0] на позиции a[i] в RMQ₀, Это означает, что существует зигзагообразная последовательность с длиной dp[i][0] все больше и больше a[i],

Затем для того, чтобы рассчитать dp[i + 1][0]Вам не нужно перебирать все числа от 0 до i, Вместо этого вы можете запросить RMQ₀ для наибольшего числа на позиции> a[i + 1], Это даст вам самую длинную зигзагообразную подпоследовательность, заканчивающуюся числом, превышающим текущую, то есть самую длинную, которая может продолжаться по убыванию с номером. a[i + 1], Тогда вы можете сделать то же самое для RMQ₁ для другой половины зигзагообразных подпоследовательностей.

Так как вы можете реализовать динамический RMQ со сложностью запроса O(log N)это дает вам общую сложность O(N log N),

Вы можете решить эту проблему в O(n) время и O(n) дополнительное пространство

Алгоритм работает следующим образом.

1. Сохраните разницу альтернативного термина в новом массиве размеров n-1
2. Теперь пройдитесь по новому массиву и просто проверьте, является ли произведение альтернативного члена меньше нуля или нет.
3. Увеличьте результат соответственно. Если во время обхода вы обнаружите, что массив — это продукт больше нуля, в этом случае вы сохраняете результат и снова начинаете считать остальную часть элемента в массиве разностей.
4. Найти максимум среди них, сохранить его в результате, и return (result+1)

Вот его реализация в C ++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
int n;
cin>>n;
vector<int> data(n);
for(int i = 0; i < n; i++)
cin>>data[i];
vector<int> diff(n-1);
for(int i = 1; i < n; i++)
diff[i-1] = data[i]-data[i-1];
int res = 1;
if( n < 2)
cout<<res<<"\n";
else
{
int temp_idx = 0;
for(int i = 1; i < n-1; i++)
{
if(diff[i]*diff[i-1] < 0)
{
temp_idx++;
res++;
}
else
{
res = max(res,temp_idx);
temp_idx = 1;
}
}
cout<<res+1<<"\n";
}
return 0;
}

Это чисто теоретическое решение. Вот как бы вы решили это, если бы вас попросили об этом в академической среде, стоящей рядом с классной доской.

Решение проблемы может быть создано с помощью динамического программирования:

Подзадача имеет вид: если у меня есть элемент x последовательности, какая самая длинная подпоследовательность заканчивается на этом элементе?

Затем вы можете разработать свое решение с помощью рекурсивных вызовов, которые должны выглядеть примерно так (направления отношений могут быть неправильными, я не проверял это):

S - given sequence (array of integers)
P(i), Q(i) - length of the longest zigzag subsequence on elements S[0 -> i] inclusive (the longest sequence that is correct, where S[i] is the last element)

P(i) = {if i == 0 then 1
{max(Q(j) if A[i] < A[j] for every 0 <= j < i)Q(i) = {if i == 0 then 0  #yields 0 because we are pedantic about "is zig the first relation, or is it zag?". If we aren't, then this can be a 1.
{max(P(j) if A[i] > A[j] for every 0 <= j < i)

Это должно быть O(n) с правильным запоминанием (сохраняя каждый вывод Q (i) и P (i)), потому что каждая подзадача вычисляется только один раз: n*|P| + n*|Q|,

Эти вызовы возвращают длину решения — фактический результат может быть найден путем хранения «родительского указателя» всякий раз, когда найдено максимальное значение, а затем обратного хода по этим указателям.

Вы можете избежать рекурсии, просто заменив вызовы функций поисками в массиве: P[i] а также Q[i]и используя for петля.