java - 获取最长凸子序列的问题

Question

如果 X[i+1] - X[i] > X[i] - X[i-1] 对于介于 2 和m-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[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

你是对的，这个问题可以用动态规划来解决。总体思路是存储以原始数组的每个元素结尾的每个可能的有效凸子序列，具有特定的最大连续元素差异，然后使用所有先前的条目构造下一个子序列。

更具体地说，构造一个二维矩阵，将以特定索引结尾的最长凸序列存储到原始数组A中，并且最多连续项之间的最大差异差异。所以 dp[3][11] 将给出以 A 的第 3 个元素结尾且不包含大于 11 的连续差异的最长凸子串。

使用此数组中的先前条目，我们可以为原始数组的第 k 元素构造行 k。只需遍历每个前面的行 j，并将 A[k] 连接到 dp[j][diff] 处的每个序列，对于 diff 范围 [0, A[k]-A[j])。将这个新序列存储在 dp[k][diff+1] 中。每当某些 diff 在 dp[k][diff+1] 发生冲突时，保留两个序列中较长的一个。

冲洗并重复此过程，直到在 A 中有一行元素元素。然后从每一行的最长子序列中取出最长的序列。最长的子序列将始终是每一行中的最后一个非空元素，因此只需向后迭代每一行，并取最长的行。这将是您最长的凸子序列。