Определить длину подмассива

Question

Определить длину подмассива

Рейтинг: 0Ответов: 2Опубликовано: 14.02.2023

Необходимо определить максимальную длину подмассива у которого все элементы возрастают: X(i) < X(i+1)

Объявил две переменные, одна содержит максимальную длину, другая хранит длину длин. Пробежался по массиву и записал в count значение. Если максимальное значение меньше count, то записал в максимальное значение count. В итоге будут посчитаны все возрастающие последовательности даже если они идут с прерыванием, но как посчитать именно подмассивы?

int max = 1;
int count = 1;

for (int i = 0; i < array.length - 1; i++) {
    if (array[i] < array[i + 1])
        count++;
}

if (max < count)
    max = count;
count = 1;

System.out.print(max + " ");

java массивы

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Почти правильно написали, только последние строки должны быть в блоке else. Т.е. пока последовательность возрастает - увеличиваем счетчик. Как только перестала возрастать (конец возрастающей последовательности/подмассива) - проверяем на максимум и запоминаем если надо, а счетчик сбрасываем в начальное значение.
И сравнение после цикла - на случай если массив завершится на увеличивающейся последовательности, то сравнение с max в цикле не сработает.

int max = 1;
int count = 1;

for (int i = 0; i < array.length - 1; i++) {
    if(array[i] < array[i+1])
        count++;
    else{
        if (max < count)
            max = count;
        count = 1;
    }
}
if (max < count)
    max = count;

Answer 2

▲ 3

Можно сразу же при инкременте счетчика запоминать максимум, также следует учесть пустой массив.
(Обновление) Также стоит дополнительно проверить условие досрочного выхода, когда размер оставшейся части массива не превышает уже подсчитанную максимальную длину:

public static int maxLength(int ... arr) {
    if (null == arr || arr.length < 1) {
        return 0;
    }
    int max = 1;
    for (int i = 1, count = 1; i < arr.length; i++) {
        if (arr[i] > arr[i - 1]) {
            if (++count > max) {
                max = count;
            }
        }
        else {
            count = 1;
            if (max >= arr.length - i) {
                break; // отбросить проверку хвоста массива
            }
        }
    }
    return max;
}

Тест:

System.out.println(maxLength());                     // 0
System.out.println(maxLength(2));                    // 1
System.out.println(maxLength(2, 3, 4, 2, 3));        // 3
System.out.println(maxLength(2, 3, 4, 2, 3, 5, 7));  // 4

Определить длину подмассива

Ответы