HW Recursive Divide and Conquer Algorithm

Question

I'm having a really big issue with finding the solution to my problem. I have to create a recursive, divide-and conquer algorithm that computes the length of the longest non-decreasing subsequence of elements in an array of integers. I have the following code, but it's not really working, any help would be much appreciated!!!

public class LongestSubSequence {

    public static int getPartition(int[] a, int p, int r)
    {
        int mid = ((p+r)/2)-1;
        int q=0;
        int i = 1;
        int j= mid+i;
        int k = mid -i;

            while (a[mid]<=a[j] && j < r)
                {
                    q = j;
                    i++;

                }

                    while (a[mid] >=a [k] && k > p)
                {
                    q = k;
                    i++;
                }

        return q;
    }

    public static int getCount (int[]a, int p, int r)
    {
        int i = p;
        int j = p+1;
        int count = 0;
        while (i<r && j<r)
        {
            if(a[i]<=a[j])
                count++;
            i++;
            j++;
        }
        return count;
    }

    public static int getLongestSubsequence (int[] a, int p, int r) {

        int count = 0;

        if (p<r)
        {
            int q = getPartition (a, p, r);
            count = getCount(a,p,r);
            if (count < getLongestSubsequence(a,p,q))
                count = getLongestSubsequence(a, p, q);
            else if (count < getLongestSubsequence(a, q+1, p))
            {
                count = getLongestSubsequence(a, q+1, p);
            }

        }


        return count;
        }

     public static int LongestSubsequence (int[] a) {
            return getLongestSubsequence(a, 0, a.length);
            }




    public static void main(String[] args) {
        int[] a = {1,3,5,9,2, 1, 3};
        System.out.println(LongestSubsequence(a));

    }

}

This is a bit extensive for what you need. The first problem I see is that the initial length of a is 7, so ((p+r)/2) is going to be 3.5 — mowwwalker
Can you define what you mean by "subsequence"? Must the elements of the subsequence be contiguous in the parent sequence? — dlev
The example they gave to define the subsequence is: if you are given a sequence 1 2 3 4 3 2 1 the longest nondecreasing subsequence is 1 2 3 4 and the method should return 4. The reason it is so drawn out (the code) is I was not sure how to make this a divide-and-conquer recursion problem. It is incredibly easy as a simple loop. I understand that p+r/2 =3.5 but it will truncate that to 3 and that works as well. I think... — user992296
if I understand it correctly, there is something wrong with the function count - its first invocation with p==0 and r==a.length, will return value higher than any other call to it with other parameters — ciamej
there's another problem with the partition function, you don't change the value of j nor k in the loops, the fact that you assign a value to i doesn't mean that it affects anyhow j or k — ciamej

jeff jeff · Accepted Answer · 2011-10-12T21:42:37

This is a pretty big body of code, and it's a little hard to follow with all the a's, r's, q's, etc.

In general, I would create an array (call it longestSeq) where longestSeq[i] is the length of the longest non-decreasing sequence found so far that starts at index, i, of your original sequence. For instance, if I had

  int[] sequence = new int[] { 3, 5, 1, 2 }

then the algorithm would yield

  longestSeq[0] = 2;
  longestSeq[1] = 1;
  longestSeq[2] = 2;
  longestSeq[3] = 1;

So you would initialize longestSeq to all 0's, and then iterate through your list and fill in these values. At the end, just take the max of longestSeq.

Maybe start with just trying to make it work iteratively (without recursion) and then add recursion if that's a requirement.

HW Recursive Divide and Conquer Algorithm

1 Answers