Проблема с получением самой длинной выпуклой подпоследовательности

Question

Последовательность X [1..m] целых чисел называется выпуклой, если X [i + 1] - X [i]> X [i] - X [i-1] для каждого целого числа i от 2 дом-1.

for (int i = 1; i < list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                dp[i][j] = 2;
                for (int k = 0; k < j; k++) {
                    if (dp[j][k] + 1 > dp[i][j] && ((list.get(i) + list.get(k)) > (list.get(j) * 2))) {
                        dp[i][j] = dp[j][k] + 1;
                    }
                    len = Math.max(len, dp[i][j]);
                }
            }
        }

Я обнаружил, что существует шаблон, который для X [1..m] определяет Y [2..m], позволяя Y [i] = X [i] - X [i-1].Таким образом, Y является последовательностью, состоящей из различий между последовательными членами X. Последовательность X является выпуклой тогда и только тогда, когда последовательность Y увеличивается.Мне интересно, есть ли способ получить подпоследовательность, например A = [0, 3, 7, 8, 13] , тогда самая длинная выпуклая подпоследовательность равна [0, 3, 7, 13].Заранее спасибо.

Answer 1

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

Более конкретно,построить двумерную матрицу, которая хранит самую длинную выпуклую последовательность, заканчивающуюся определенным index, в исходный массив A и наибольшую разницу между последовательными членами не более diff.Таким образом, dp[3][11] даст самую длинную выпуклую подстроку, которая заканчивается 3-м элементом A и не содержит последовательных различий больше 11.

Используя предыдущие записи в этом массиве, мы можем построить строку k для k-го элемента вашего исходного массива.Просто выполните итерацию по каждой предыдущей строке j и объедините A[k] с каждой последовательностью в dp[j][diff], для diff в диапазоне [0, A[k]-A[j]).Сохраните эту новую последовательность в dp[k][diff+1].Всякий раз, когда случается столкновение в dp[k][diff+1] для некоторых diff, сохраняйте самую длинную из двух последовательностей.

Промойте и повторяйте этот процесс, пока у вас не будет строки для элемента element в A.Затем просто возьмите самую длинную последовательность из самой длинной подпоследовательности каждого ряда.Самая длинная подпоследовательность всегда будет последним непустым элементом в каждой строке, поэтому просто переберите каждую строку в обратном направлении и возьмите самую длинную из строк.Это будет ваша самая длинная выпуклая подпоследовательность.