История изменений
Исправление alysnix, (текущая версия) :
правильный алгоритм такой:
1 сортируешь массив по возрастанию.
- начиная с левого конца идешь индексом и смотришь, что текущее число на 1 больше предыдущего. пока оно так - увеличиваешь длину текущей подстроки. как только оно не так - ты получил монотонную подстроку, ее начало и длину. сравниваешь с предыдущей максимальной подстрокой, если меньше, начинаешь сканирование новой подстроки с текущего индекса. если длина больше - заменяешь начало и длину максимальной(искомой) подстроки и, начинаешь сканирование с текущего индекса.
тут только один проход, нет повторного сканирования, ты просто проверяешь монотонного возрастание текущего числа. это O(n).
итого сортировка массива (n*log n) + один проход (n), с просмотром на одно число вперед.
наихудший случай, это когда нет ни одной монотонной последовательности. и чем больше монотонных последовательностей там - тем быстрей.
Исправление alysnix, :
правильный алгоритм такой:
1 сортируешь массив по возрастанию.
- начиная с левого конца идешь индексом и смотришь, что текущее число на 1 больше предыдущего. пока оно так - увеличиваешь длину текущей подстроки. как только оно не так - ты получил монотонную подстроку, ее начало и длину. сравниваешь с предыдущей максимальной подстрокой, если меньше, начинаешь сканирование новой подстроки с текущего индекса.
тут только один проход, нет повторного сканирования, ты просто проверяешь монотонного возрастание текущего числа. это O(n).
итого сортировка массива (n*log n) + один проход (n), с просмотром на одно число вперед.
наихудший случай, это когда нет ни одной монотонной последовательности. и чем больше монотонных последовательностей там - тем быстрей.
Исходная версия alysnix, :
правильный алгоритм такой:
1 сортируешь массив по возрастанию.
- начиная с левого конца идешь индексом и смотришь, что текущее числа на 1 больше предыдущего. пока оно так - увеличиваешь длину текущей подстроки. как только оно не так - ты получил монотонную подстроку, ее начало и длину. сравниваешь с предыдущей максимальной подстрокой, если меньше, начинаешь сканирование новой подстроки с текущего индекса.
тут только один проход, нет повторного сканирования, ты просто проверяешь монотонного возрастание текущего числа. это O(n).
итого сортировка массива (n*log n) + один проход (n), с просмотром на одно число вперед.
наихудший случай, это когда нет ни одной монотонной последовательности. и чем больше монотонных последовательностей там - тем быстрей.