наибольший возрастающий или убывающий фрагмент массива,

здравствуйте у меня проблема, хочу получить наибольший возрастающий или убывающий фрагмент массива,

Например, дан массив 1, 3, 2, 0.

Итого, самый длинный фрагмент имел длину 3 (3,2,0). Это и есть ответ.

для "1,10,2,10,3,10,4,10" вернуть 2), а для "5,4,3,2,1"


Ответы (1 шт):

Автор решения: BccHnw

Есть несколько вариантов. Вариант с запоминанием знака для поиска максимальной длины строго возрастающей или строго убывающей последовательности:

public class Main {
    public static int findSequenceLength(int[] arr) {
        int arrayLen = arr.length;
        if (arrayLen == 0)
            return 0;
        if (arrayLen == 1)
            return 1;
        int maxLen = 1;
        int len = 1;
        int prev = arr[0];
        int sign = 0;
        for (int i = 1; i < arrayLen; i++ ){
            int value = arr[i];
            if (value > prev) {
                if (sign > 0) {
                    len = len + 1;
                }
                else {
                    len = 2;
                    sign = 1;
                }
            }
            else if (value < prev) {
                if (sign < 0) {
                    len = len + 1;
                }
                else {
                    len = 2;
                    sign = -1;
                }
            }
            else {
                len = 1;
                sign = 0;
            }
            if (len > maxLen) maxLen = len;
            prev = value;
        }
        return maxLen;
    }
    public static void main(String[] args) {
        int[] arr0 = new int[]{1, 3, 2, 0};
        System.out.println(findSequenceLength(arr0));
        int[] arr1 = new int[]{1, 10, 2, 10, 3, 10, 4, 10};
        System.out.println(findSequenceLength(arr1));
        int[] arr2 = new int[]{5, 4, 3, 2, 1};
        System.out.println(findSequenceLength(arr2));
        int[] arr3 = new int[]{0, 0, 1, 0, 1, 1};
        System.out.println(findSequenceLength(arr3));
    }
}

У пустого массива длина искомой последовательности всегда 0. У массива с одним элементом - 1 (сам единственный элемент).

Если знак поменялся, а элементы не равны, то длина искомой последовательности уже как минимум 2 (сами эти два элемента). Легко, кстати, доказать, что у непустого массива длина искомой последовательности будет 1 тогда и только тогда, когда все элементы равны между собой.

Если нужно найти начало искомой подпоследовательности, то предлагается код исправить самостоятельно (это несложно).

→ Ссылка