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.

Может быть, сначала просто попытаться заставить его работать итеративно (без рекурсии), а затем добавить рекурсию, если это необходимо.