Problem with getting Longest Convex Subsequence

Question

A sequence X[1..m] of integers is said to be convex if X[i+1] - X[i] > X[i] - X[i-1] for every integer i between 2 and 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]);
                }
            }
        }

I have found there is a pattern that Given X[1..m], define Y[2..m] by letting Y[i] = X[i] - X[i-1]. Thus, Y is the sequence consisting of differences between successive terms of X. The sequence X is convex if and only if the sequence Y is increasing. I am wondering is there any way to get the subsequence like A = [0, 3, 7, 8, 13], then a longest convex subsequence is [0, 3, 7, 13]. Thanks in advance.

should the longest subsequence not be [0, 3, 7] (or [7, 8, 13] for that matter), or do you want to remove all data points that would break the convexness? — luk2302
I want to remove all data points that would break the convexness. — Yifdaddy
Or it would be better to say I want to have a new array that contains the longest convex subsequence. — Yifdaddy

Dillon Davis Dillon Davis · Accepted Answer · 2019-03-25T01:04:31

You are right in that this problem can be solved by dynamic programming. The general idea is to store the each possible valid convex subsequence that ends with each element of the original array with a specific max consecutive element difference, and then use all prior entries to construct the next subsequence.

More specifically, construct a 2D matrix that stores the longest convex sequence ending with at a specific index into the original array A and largest difference between successive terms at most diff. So dp[3][11] would give the longest convex substring which ends with the 3rd element of A, and contains no successive differences larger than 11.

Using prior entries in this array, we can construct the row k for the kth element of your original array. Just iterate through each prior row j, and concatenate A[k] to each sequence at dp[j][diff], for diff in range [0, A[k]-A[j]). Store this new sequence in dp[k][diff+1]. Whenever there happens to be a collision at dp[k][diff+1] for some diff, keep the longer of the two sequences.

Rinse and repeat this process until you have a row for element element in A. Then just take the longest sequence out of the longest subsequence of each row. The longest subsequence will always be the last non-empty element in each row, so just iterate over each row backwards, and take the longest of the rows. This will be your longest convex subsequence.

Problem with getting Longest Convex Subsequence

1 Answers