База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C

Най-дълга нарастваща подредица (LIS)

LIS е най-дългата строго нарастваща подредица, която запазва реда на входните елементи, без те да трябва да са съседни. Примерът на C изчислява дължината ѝ чрез динамично програмиране за време O(n²) и с O(n) допълнителна памет.

Версия: C23; repository compiler flag, production runtime not attested

Синтаксис

dp[i] = max({1} union {dp[j] + 1 | 0 <= j < i and a[j] < a[i]}); LIS length = n == 0 ? 0 : max(dp)

Longest increasing subsequence (LIS), или най-дълга нарастваща подредица, избира елементи в първоначалния им ред. Елементи могат да се пропускат; изборът не е задължително непрекъснат. За {3, 1, 2, 2, 4} подредицата {1, 2, 4} има максимална дължина 3. Сортирането на входа би променило задачата, защото първоначалният ред ще се загуби.

Разликата strictly increasing versus non-decreasing означава, че строго нарастващата подредица изисква <, докато ненамаляващата допуска <=. Равните стойности не удължават LIS. Замяната на a[j] < a[i] с a[j] <= a[i] дава алгоритъм за най-дългата ненамаляваща подредица; дължината ѝ за входа от примера е 4.

Нека dp[i] е дължината на най-добрата подредица, завършваща точно при a[i]. Инициализирайте я с 1. За всяко j < i, за което е изпълнено a[j] < a[i], разгледайте dp[j] + 1. Изчислявайте състоянията отляво надясно и запазвайте най-големия резултат. Вложените цикли изискват време O(n²), а масивът dp използва O(n) допълнителна памет.

Примерът връща само дължината. Запазването на индексите на предшествениците не е задължително: при непразен вход можете да възстановите LIS от a и dp. Започнете, като изберете a[i] при индекс i, за който dp[i] е максимално. Обхождайте индексите назад и избирайте a[j], когато са изпълнени j < i, a[j] < a[i] и dp[j] + 1 == dp[i]. След всеки избор задавайте на i стойността на j. Спрете, когато dp[i] == 1, и обърнете реда на избраните елементи.

Извикващият предоставя неприпокриващи се масиви a и dp, всеки с поне n елемента. При n == 0 функцията връща 0, без да достъпва който и да е от масивите, затова NULL е допустим. Не се използват динамично заделяне на памет или масиви с променлива дължина.

Примери

#include <stddef.h>
#include <stdio.h>

/* For n > 0, a and dp must each provide at least n elements.
   Their storage must not overlap. For n == 0, both may be NULL. */
static size_t lis_length(const int *a, size_t n, size_t *dp)
{
    size_t best = 0;
    for (size_t i = 0; i < n; ++i) {
        dp[i] = 1;
        for (size_t j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > best) {
            best = dp[i];
        }
    }
    return best;
}

int main(void)
{
    const int a[] = {3, 1, 2, 2, 4};
    size_t dp[sizeof a / sizeof a[0]];
    printf("LIS length: %zu\n", lis_length(a, sizeof a / sizeof a[0], dp));
    printf("Empty length: %zu\n", lis_length(NULL, 0, NULL));
    return 0;
}

Резултат

LIS length: 3
Empty length: 0

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници