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; } |
Свежие комментарии