Нужна помощь дает рекурсивное определение

Question

дана последовательность неупорядоченных п целых чисел, S = a1, a2, a3 ...

Дайте формальное и рекурсивное определение длины самой длинной неубывающей подпоследовательности в срок п.

Итак, мои мысли состоят в том, что если мы определяем его рекурсивно, то каждое целое число в последовательности является последовательностью длины 1 и содержит неубывающую подпоследовательность длины 1. Будет ли это правильным способом сказать это или я полностью выключен?

Answer 1

Я думал об этом решении. Я написал его в псевдокоде.

define function non_decreasing_subsequence (index, sub_sequence, initial_sequence) 
{ 
    sub_sequence.add(index) 

    if initial_sequence[index+1] is not defined 
     return lenght of sub_sequence 

    if initial_sequence[index] <= initial_sequence[index+1] 
     call non_decreasing_subsequence (index+1, sub_sequence, initial_sequence) 
    else 
     return lenght of sub_sequence 
} 

for i between 1 and lenght of initial_sequence 
    call non_decreasing_subsequence (i, empty_sequence, initial_sequence) 

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

Answer 2

Вероятно, лучше иметь две переменные в вашей рекурсии в дополнение к тому, на каком элементе вы находитесь. Один с историческим максимумом и один с текущей длиной восходящих элементов. Если у массива есть элемент, вам гарантирован 1 и подсчет до тех пор, пока следующий элемент не уменьшится, то вы перезапустите, возможно, с новым историческим максимумом, или в конце вы вернете максимальную текущую длину и исторический максимум.

Что-то вроде этой реализации схемы?

(define (longest-increasing-sequence lst) 
    (if (null? lst) 
     0 
     (let recur ((lst lst) (cur 1) (hmax 0)) 
     (cond ((null? (cdr lst)) (max hmax cur)) 
       ((<= (car lst) (cadr lst)) (recur (cdr lst) (+ cur 1) hmax)) 
       (else (recur (cdr lst) 1 (max hmax cur))))))) 

А вот PHP версии одного и того же с использованием массивов вместо связанных списков:

function longest_increasing_sequence($lst) 
{ 
    $stop = count($lst)-1; 
    if($stop < 0) 
     return 0; 

    // makes an anonymous function closed over &$lst, $stop and &$recur 
    $recur = function($idx, $cur_len, $max_len) use (&$lst, $stop, &$recur) 
      { 
       $new_idx=$idx+1; 

       if($idx == $stop) 
        return max($cur_len, $max_len); 
       elseif($lst[$idx] <= $lst[$new_idx]) 
        return $recur($new_idx, $cur_len + 1, $max_len); 
       else 
        return $recur($new_idx, 1, max($cur_len, $max_len)); 
      }; 

    // start recursion 
    return $recur(0, 1, 0); 
} 

Answer 3

Чисто рекурсивным:

-module(lndss). 

-export([get_len/1]). 

get_len([]) -> 0; 
get_len([H|T]) -> get_len(H, T, 1, 1). 

get_len(_, [], C, M) -> max(C, M); 
get_len(P, [H|T], C, M) when H < P -> get_len(H, T, 1, max(C, M)); 
get_len(_, [H|T], C, M) -> get_len(H, T, C+1, M).