HW递归分治算法

Question

我在寻找解决问题的方法方面遇到了一个非常大的问题。我必须创建一个递归的分治算法来计算整数数组中元素的最长非递减子序列的长度。我有以下代码，但它不是真的工作，任何帮助将非常感激!!

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));
    }
}

Answer 1

这是一段相当大的代码体，使用所有的a, r, q等等，有点难以理解。

一般来说，我会创建一个数组(称为longestSeq)，其中longestSeq[I]是迄今为止发现的从原始序列的索引I开始的最长非递减序列的长度。例如，如果我有

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

则算法将生成

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

因此，您将初始化longestSeq为所有0，然后遍历列表并填充这些值。最后，取longestSeq的最大值。

也许一开始只是试着让它迭代工作(没有递归)，然后添加递归，如果这是一个要求。