Самый длинный увеличивающийся подмассив в Окамле

Question

Я пытаюсь найти решение для следующей проблемы: написать функцию в OCaml, у которой в качестве выходных данных указан первый и последний индексы самого длинного увеличивающегося подмассива.Я борюсь с исправлением ошибок.Пока я написал это:

Пример:

longest_increasing_subarray [|2;4;6;9;1;5;3;5;0;8;9;13;17|];;
- : (8,12)

Это мой код:

let longest_increasing_subarray p1 =
  let n = Array.length p1
  and beg = ref 0
  and larg = ref(0,0) in
  for i=0 to n-1 do begin
    if i=0 then begin
    end;
    if p1.(i-1)<p1.(i) then
      begin
        if (snd !larg - fst !larg +1)<((i-1)-(!beg+1)) then
          !larg = (!beg,i-1)
            !beg = i end;
    if (i=n-1) then
      begin if (snd !larg-fst !larg +1)<((i)-(!beg)+1) then
          !larg := (!beg,i)
      end;
  end;
  done;
  !larg;;

Answer 1

Есть несколько проблем с вашим кодом и вашим подходом, позвольте мне выделить их в форме вопросов и ответов:

1. Как назначить значение для ссылки

   • Правильно:

     x := v
     

   • Неправильно:

     x = v
     !x = v
     !x := v
     

2. Как сделать дваназначения подряд

   • Правильно:

     x := v;
     y := p
     

   • Неправильно:

     x := v
     y := p
     

3. Как перейти на условие

   • Правильно:

     if p1.(i - 1) < p1.(i) 
     then update_indices i;
     else reset_indices ();
     

   • Неправильно:

     if p1.(i - 1) < p1.(i) 
     then begin update_indices i end
     reset_indices ()
     

4. Как изучать OCaml

   • Правильно: прочитайте Руководство по OCaml и другие книги
   • Неправильно: пост на SO в надежде, что кто-то даст вам коды

5. Как реализовать функцию longest_increasing_subarray

   • Исправить:

    Use a recursive function `find_longest` that will have four parameters:
       - `p` - the beginning of the longest sequence;
       - `q` - the end of the longest sequence; 
       - `s` - the beginning of the current working hypothesis
       - `t` - the end of the current working hypothesis;
       - `i` - the array index;
    The longest increasing sequence in the array `a` is defined as
    `find_longest 0 0 0 0 1`. The `find_longest` has the following definiton:
       - if `i >= Array.length a` then the result is 
          - `(p,q)` if `p - q > t - s` 
          - `(s,t)` otherwise
       - else if `a.(i-1) < a.(i)` then the result is `find_longest p q s i (i+1)`
       - else if `q - p < t - s` then the result is `find_longest s t i i (i+1)`
       - else the result is `find_longest p q i i (i+1)` 

• Неправильно: используйте обязательные циклы for, ссылки и т. Д.