У меня есть следующий алгоритм, который хорошо работает

Я попытался объяснить это здесь для себяhttp://nemo.la/?p=943 и это объясняется здесьhttp://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ а также и на stackoverflow, а также

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

для последовательности 30 20 20 10 10 10 10

ответ должен быть 4: «10 10 10 10»

Но с nlgn версией алгоритма он не работает. Инициализация s, чтобы содержать первый элемент "30" и запуск со второго элемента = 20. Вот что происходит:

Первый шаг: 30 не больше или не равен 20. Мы находим наименьший элемент больше 20. Новый s становится «20»

Второй шаг: 20 больше или равен 20. Мы расширяем последовательность, и теперь s содержит «20 20».

Третий шаг: 10 не больше или не равен 20. Мы находим наименьший элемент больше 10, который равен «20». Новый с становится "10 20"

и s никогда не будет расти после этого, и алгоритм вернет 2 вместо 4

int height[100];
int s[100];

int binary_search(int first, int last, int x) {

    int mid;

    while (first < last) {

        mid = (first + last) / 2;

        if (height[s[mid]] == x)
            return mid;

        else if (height[s[mid]] >= x)
            last =  mid;

        else
            first = mid + 1;
    }
    return first; /* or last */
}

int longest_increasing_subsequence_nlgn(int n) {

    int i, k, index;

    memset(s, 0, sizeof(s));

    index = 1;
    s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length  i = 1 */

    for (i = 1; i < n; i++) {

        if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */

            index++; /* increase the length of my subsequence */
            s[index] = i; /* the current doll ends my subsequence */

        }
        /* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */
        else {
            k = binary_search(1, index, height[i]);

            if (height[s[k]] >= height[i]) { /* if truly >= greater */
                s[k] = i;
            }
        }
    }
    return index;
}