Блог

Мне нужно решить эту проблему с помощью DP, и вот в чем проблема: у нас есть массив, и мы хотим создать подмассив с возрастанием максимального размера с 2 условиями:

1. Мы можем просто обойти массив один раз слева направо.
2. У нас есть только два допустимых хода, чтобы создать этот подмассив :
   • Мы можем игнорировать следующий элемент в массиве при обходе
   • Мы можем поместить следующий элемент в конец или начало массива, и этот массив должен быть в порядке возрастания

например,:

ввод : arr[ ] = {0 , 3 , 10 , 7 , 6 , 5 , 14}

вывод : 5

и подмассив {5 , 6, , 7 , 10 , 14}

Решение для этого экземпляра таково: начните с 10, затем поместите 7 слева, а 6 и 5 слева, затем поместите 14 справа от 10

Это означает, что мы можем расширить массив по этим условиям слева и справа

Ну, это классическая проблема dp, которую довольно просто решить с помощью нисходящего подхода.

давайте определим наше состояние dp [c] [dec] [inc] — теперь мы смотрим на элемент в позиции c, элемент в конце последовательности, которую мы построили, находится в позиции dec, а элемент в начале последовательности находится в позиции inc.

Итак, теперь мы можем перейти к:

• dp [c 1][dec] [inc] путем пропуска текущего элемента
• dp[c 1][c] [inc] путем помещения текущего элемента в конец (допустимо, только если a[c] <= a[dec])
• dp[c 1][dec] [c] путем размещения текущего элемента впереди (допустимо, только если a [c] >= a [inc])

пример кода (C ) :

 const int n = 7;
int a[] = {0, 0, 3, 10, 7, 6, 5, 14};
int dp[n 1][n 1][n 1];

int solve(int c, int dec, int inc)
{
    if(c > n)return 0;
    if(dp[c][dec][inc] != -1)return dp[c][dec][inc];

    dp[c][dec][inc] = solve(c 1,dec,inc); //skip element
    if(inc==0 amp;amp; dec==0) //if our sequence is empty, try appending element to sequence
        dp[c][dec][inc] = max(dp[c][dec][inc], 1   solve(c 1,c,c));
    else if(a[c] >= a[inc])//we can extend our array [dec, ..., inc] because current element can be put to front
        dp[c][dec][inc] = max(dp[c][dec][inc], 1   solve(c 1,dec,c));
    else if(a[c] <= a[dec])//we can extend our array [dec, ..., inc] because current element can be put to back
        dp[c][dec][inc] = max(dp[c][dec][inc], 1   solve(c 1,c,inc));

    return dp[c][dec][inc];
}

int main()
{
    memset(dp, -1, sizeof dp);
    cout<<solve(1,0,0);
}
 

Сложность O (n ^ 3)