Algorithm help -- Longest Convex Subsequence

Discussion in 'Mac Programming' started by ravenvii, Nov 8, 2014.

  1. ravenvii macrumors 604

    ravenvii

    Joined:
    Mar 17, 2004
    Location:
    Melenkurion Skyweir
    #1
    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:

    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.
     
  2. aaronvan Suspended

    aaronvan

    Joined:
    Dec 21, 2011
    Location:
    República Cascadia
    #2
    Most people say the two required algorithm courses are the most difficult in our MSCSS program. Thank's for the confirmation!
     
  3. dmi macrumors regular

    Joined:
    Dec 21, 2010
    #3
    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)
     

Share This Page