наибольший возрастающий или убывающий фрагмент массива,
здравствуйте у меня проблема, хочу получить наибольший возрастающий или убывающий фрагмент массива,
Например, дан массив 1, 3, 2, 0.
Итого, самый длинный фрагмент имел длину 3 (3,2,0). Это и есть ответ.
для "1,10,2,10,3,10,4,10" вернуть 2), а для "5,4,3,2,1"
Ответы (1 шт):
Есть несколько вариантов. Вариант с запоминанием знака для поиска максимальной длины строго возрастающей или строго убывающей последовательности:
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 тогда и только тогда, когда все элементы равны между собой.
Если нужно найти начало искомой подпоследовательности, то предлагается код исправить самостоятельно (это несложно).