Создание вложенного массива максимальной длины по возрастанию из массива только с 3 допустимыми ходами

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

  1. Мы можем просто пройтись по массиву один раз слева направо.
  2. We have just two valid moves to make this sub array :
    • We can ignore the next element in array in the traverse
    • Мы можем поместить следующий элемент в конец или начало массива, и этот массив должен быть в порядке возрастания.

например:

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

вывод: 5

и вспомогательный массив {5 , 6, , 7 , 10 , 14}

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

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


arrays algorithm maxlength dynamic-programming sub-array
person Mohammad Mahdi Mohajer    schedule 14.04.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

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 && 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)

person Photon    schedule 14.04.2019