Задача с ШАДа
Дается массив a. Найдите длину максимально чередующейся подпоследовательности.
Максимальная чередующая подпоследовательность - это набор индексов i1, i2, .., ik где k максимальное и a[i1] < a[i2] > a[i3] < a[i4] > a[i5] < .... a[ik], а также i1 < i2 < i3 < ... < ik

Решение:
Решать будем через динамическое программирование.
Пусть dp[i][0] - длина максимальной чередующей подпоследовательности, которая заканчивается на позицию i, а также знак до числа a[i] был <
dp[i][1] - определим также как и dp[i][0], но знак до a[i] был >
Базой будет dp[i][j] = -INF для всех i, j, а также dp[i][1] = 1 для всех i, (0 <= i < n)

Переходы: dp[i][0] = max(dp[i][0], dp[j][1] + 1) для всех j < i и a[j] < a[i], аналогично и dp[i][1] = max(dp[i][1], dp[j][0] + 1) для всех j < i и a[j] > a[i].

Такое решение работает за O(n^2). На самом деле это можно оптимизировать с помощью дерево отрезков до n*logn но решение за квадрат принимали.