Javascript задача. Максимальная неубывающая последовательность чисел в массиве
Задача.
Напишите сценарий, определяющий максимальную по длине неубывающую последовательность чисел в массиве:
Алгоритм решения
Циклом идем по массиву. Сохраняем последовательности чисел во временный массив tmp_arr
. Т.е., если значение текущего элемента массива больше или равно предыдущему, то помещаем его во временный массив tmp_arr
. Как только текущий элемент становится меньше предыдущего – значит неубывающая последовательность закончилась и переходим к сравнению длин массивов tmp_arr
и seq_arr
В этих массивах хранятся текущая неубывающая последовательность и предыдущая соответственно. Если размер массива tmp_arr
, а соответственно и длина текущей последовательности чисел больше предыдущей, то сохраняем текущую последовательность в seq_arr
. В итоге, после цикла в массиве seq_arr
будет храниться максимальная неубывающая последовательность чисел из заданного массива arr
.
Код javascript:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
var arr = [1,2,3,4,5,0,7,8,9,10,0,1,2,10,20,1,2,3,4,5,6,7,5,4,3,2,1,3,5,6,8,8]; function max_sequence(arr) { var seq_arr = [arr[0]]; var tmp_arr = [arr[0]] for (i = 1; i < arr.length; i++) { if (arr[i] >= arr[i-1]) { tmp_arr.push(arr[i]); } else { if (tmp_arr.length > seq_arr.length) { seq_arr = tmp_arr; } tmp_arr = [arr[i]]; } } if (tmp_arr.length > seq_arr.length) { seq_arr = tmp_arr; } return seq_arr; } document.write(max_sequence(arr)); |
Если в заданном массиве arr
будет две последовательности чисел, которые окажутся максимальными по длине, то в данной реализации будет выдана первая максимальная последовательность, если нужно выводить последнюю, то в код нужно внести такое изменение при сравнении длин массивов (вместо знака > написать >=).
1 2 3 4 5 6 7 |
if (tmp_arr.length >= seq_arr.length) { seq_arr = tmp_arr; } |
Свежие комментарии