18

class Main
{
    // Функция для нахождения длины самой длинной убывающей подпоследовательности
    // подмассива `nums[i…n)`
    public static int LDS(int[] nums, int i, int prev)
    {
        // Базовый случай: ничего не осталось
        if (i == nums.length) {
            return 0;
        }

        // случай 1: исключить текущий элемент и обработать
        // оставшиеся элементы
        int excl = LDS(nums, i + 1, prev);

        // случай 2: включить текущий элемент, если он меньше
        // чем предыдущий элемент в LDS
        int incl = 0;
        if (nums[i] < prev) {
            incl = 1 + LDS(nums, i + 1, nums[i]);
        }

        // вернуть максимум из двух вышеперечисленных вариантов
        return Integer.max(incl, excl);
    }

    public static void main(String[] args)
    {
        int[] nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };

        System.out.println("The length of the LDS is " +
                    LDS(nums, 0, Integer.MAX_VALUE));
    }
}