Рекурсивный алгоритм "разделяй и властвуй" для получения самого длинного неубывающего массива чисел

#algorithm

#алгоритм

Вопрос:

У меня возникли серьезные проблемы с этой проблемой. Мне нужен рекурсивный алгоритм, который «делит и побеждает», который сообщает мне длину самого длинного неубывающего массива чисел. Лично я бы предпочел использовать этот код, который я написал, прежде чем внимательно прочитать вопрос.

  int bestIndex = 0;
    int bestLength = 0;
    int curIndex = 0;
    int curLength = 1;

    for (int i = 1; i < a.length; i   ){
        if (a[i] >= a[i-1]){
            curLength   ;
        }else {
            curLength = 1;
            curIndex = i;
        }
        if (curLength > bestLength){
            bestIndex = curIndex;
            bestLength = curLength;
        }
    }
    return bestLength;

Проблема в том, что задание требует, чтобы я использовал «разделяй и властвуй», и я не могу придумать способ сделать это.

Примером является «4 2 3 3 1 2 4 5 9 2» Он вернет «5» из-за «1 2 4 5 9».

Любая помощь приветствуется.

Спасибо

1. пройдите по списку и выберите «точку разделения», которая будет находиться там, где происходит уменьшение. Однако на самом деле это не будет «разделением», если вы не выберете точку разделения вблизи середины. Я бы начал с середины, а затем повторил бы наружу. цикл с i = m (средний), затем m-1, m 1, m-2, m 2 и т. Д., Пока не произойдет уменьшение между i и i 1. Затем разрежьте массив пополам и выполните рекурсию по каждой из половин. Если уменьшений не существует, верните длину последовательности.

Ответ №1:

Вы уверены, что подмассивы должны состоять из смежных элементов? Эта проблема становится более интересной для подпоследовательностей…

В любом случае, если вам нужен алгоритм «разделяй и властвуй», попробуйте следовать базовому плану:

 function f(array) =
    if array is empty or constant size or something like that
        handle base case
    else
        result1 <- f(first half of the array)
        result2 <- f(second half of the array)
        return some_way_to_combine(result1, result2)

Конечно, вам нужно правильно выбрать, что f должно вернуть, чтобы помочь вам. Вам нужно будет обрабатывать как случаи, когда увеличивающийся подмассив находится внутри одной из половин, так и случай, когда он пересекает границу.

Ответ №2:

Другой ответ — это хороший общий ответ.

Тем не менее, я собираюсь предположить, что ключевым моментом является знание того, на какие вопросы вы должны быть в состоянии ответить при объединении результатов. Если результат 1 представляет массив [i, j], а результат 2 представляет [j 1, k], то это те вопросы, на которые вам нужно ответить:

Какова самая длинная неубывающая последовательность, которая заканчивается на j?
Какая самая длинная неубывающая последовательность, начинающаяся с j 1?
Какую последовательность максимальной длины я видел до сих пор (включая последовательности, которые заканчиваются на j и начинаются с j 1)?

Если вы предполагаете, что уже можете ответить на эти вопросы для result1 и result2, то вы должны быть в состоянии определить ответы для вашего объединенного результата [i, k] (т. Е. Самая длинная последовательность, начинающаяся с i, и самая длинная, начинающаяся с k, а также самая длинная, которую вы когда-либо видели, включая эти две).