macOS Algorithm help -- Longest Convex Subsequence

[ravenvii]

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:

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.

 

[aaronvan]

Most people say the two required algorithm courses are the most difficult in our MSCSS program. Thank's for the confirmation!

 

[dmi]

You can form an O(n^3) DAG of all possible convex sequences, and then find the longest path in that DAG in O(O(n^3)^1)