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

Question

Проблема заключается в следующем: Учитывая, что последовательность L из n целых чисел не обязательно различна, напишите алгоритм, который вычисляет возрастающую подпоследовательность максимальной длины:

Уравнение повторения, которое я разработал, таково:

Я начинаю индекс с 0:

If j = n opt(j) = 0 (base case)
otherwise opt(j) = max j <i <= n such that Lj <Li = {opt(i) +1}

Как вы думаете, это правильно? стандартное решение, используемое для этой типичной задачи, состоит в том, чтобы сначала рассчитать максимальное увеличение подпоследовательности, заканчивающееся в Li для всех элементов последовательности, а затем максимальное значение для этих значений, то есть

if i = 1 opt (i) = 1
otherwise opt (i) = max 1 <= j <= i-1 and Lj <Li = {opt (i)} +1

и затем максимум на этих элементах.

поэтому я хотел знать, считаете ли вы, что мое решение в любом случае было правильным.

Answer 1

Вот подсказка: инвариант цикла, который будет пытаться сохранить в алгоритме, состоит в том, что переменная k = индекс начала самой длинной увеличивающейся подпоследовательности. Поэтому, перебирая последовательность целых чисел [0 ... n], вы соответственно увеличиваете значение k.

Answer 2

// Учитывая массив целых чисел, найдите длину самой длинной возрастающей подпоследовательности и выведите последовательность.

int longsub (int a[], int len) {

    int localsum = 0;
    int i = 0;
    int begin = i;
    int localsublen = 1;
    int globalsunlen = 0;
    int end = i;

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

        if (a[i] > a[i-1]) {
              localsublen++;
        }
        else {
            newbegin = i;
            localsublen = 1;
        }

        if (localsublen > globalsublen)    {
            begin = newbegin;
            end = i;
            globalsublen = localsublen;
        }
    }

    for (i=begin;i <= end; i++)    
        printf ("%d.\n",a[i]);


}