Note: Yes, this is (was) homework. It was due last night, and I just gave up and submitted what I had. But it's bothering the crap out of me, so I'm going to go ahead and ask if any of you have a solution to this problem.
The problem is:
Suppose we are given an input array of integers, how to find the longest convex subsequence that satisfies the following condition:
c < (c[i-1] + c[i+1]) / 2
c[i-1], c and c[i+1] are three consecutive elements in the subsequence.
For example, if input array is { 1, 2, -1, 0, 3, 8, 5 }, the longest convex subsequence should be: 5 ({ 1, -1, 0, 3, 8 } or { 2, -1, 0, 3, 8 }).
The algorithm must be O(n^3).
My attempt:
I understand why my code doesn't work (it only checks whether there's a chain between L and R, and nothing more. It doesn't check whether it can be part of a previous chain). But I have no idea how to actually solve it.
The problem is:
Suppose we are given an input array of integers, how to find the longest convex subsequence that satisfies the following condition:
c < (c[i-1] + c[i+1]) / 2
c[i-1], c and c[i+1] are three consecutive elements in the subsequence.
For example, if input array is { 1, 2, -1, 0, 3, 8, 5 }, the longest convex subsequence should be: 5 ({ 1, -1, 0, 3, 8 } or { 2, -1, 0, 3, 8 }).
The algorithm must be O(n^3).
My attempt:
Code:
private static int LongestConvexSubseq(int n, int[] A) {
// If there are only two inputs or less, just return n
if(n < 2) {
return n;
}
int S[][] = new int[n][n];
int tmp = 0;
// Initializing the diagonal of S
for(int L = 0; L < n; L++) {
S[L][L] = 1;
}
// For every beginning point...
for(int d = 1; d < n; d++) {
// For every left-most value...
for(int L = 0; L < n-d; L++) {
// Set R to the right-most value...
int R = L + d;
// Every subsequence contains the sub-subsequences
S[L][R] = S[L][R-1];
// For every k between L and R...
for(int k = L+1; k <= R-1; k++) {
// Determine if there exists a convex between L and R
if(A[L] + A[R] >= 2 * A[k]) {
tmp = S[L][k] + 1;
}
// Stores the maximum value found in S
if(S[L][R] < tmp) {
S[L][R] = tmp;
tmp = 0;
}
}
}
}
// Returns the highest value in S
return S[0][n-1];
}I understand why my code doesn't work (it only checks whether there's a chain between L and R, and nothing more. It doesn't check whether it can be part of a previous chain). But I have no idea how to actually solve it.
