获取最长凸子序列的问题

Question

如果 X[i+1] - X[i] > X[i] - X[i-1] 对于 2 和 m-1 之间的每个整数 i，则称整数序列 X[1..m] 为凸。

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[i] = X[i] - X[i-1]来定义Y[2..m]。因此，Y 是由 X 的连续项之间的差值组成的序列。当且仅当序列 Y 增加时，序列 X 是凸的。我想知道有没有办法得到像A = [0， 3， 7， 8， 13]这样的子序列，那么最长的凸子序列是[0， 3， 7， 13]。提前致谢。

Answer 1

你是对的，因为这个问题可以通过动态编程来解决。一般思想是存储每个可能的有效凸子序列，该子序列以具有特定最大连续元素差的原始数组的每个元素结尾，然后使用所有先前的条目来构造下一个子序列。更具体地说，构建一个2D矩阵，该矩阵将最长的凸序列以特定值结尾存储到原始数组中，并且最多连续项之间的最大差值。因此，将给出最长的凸子字符串，该子字符串以 的第 3 个元素结尾，并且不包含大于 11 的连续差。indexAdiffdp[3][11]A使用此数组中的先前条目，我们可以为原始数组的第 th 个元素构造行。只需循环访问每个前一行，并连接到 ，for 范围内 的每个序列。将此新序列存储在 中。每当碰巧有碰撞时，保持两个序列中较长的一个。kkjA[k]dp[j][diff]diff[0, A[k]-A[j])dp[k][diff+1]dp[k][diff+1]diff冲洗并重复此过程，直到 在 中有一行元素元素。然后，只需从每行的最长子序列中取出最长的序列即可。最长的子序列将始终是每行中的最后一个非空元素，因此只需向后循环访问每行，并采用最长的行。这将是最长的凸子序列。A