Найти самую длинную последовательность в массив Java
Учитывая этот массив
int [] myArray = {5,-11,2,3,14,5,-14,2};
Я должен быть в состоянии вернуть 3, потому что самая длинная нисходящая последовательность-14,5, -14. Какой самый быстрый способ сделать это?
ЗЫ: последовательность-это серия не увеличивается.
6 ответов:
Просто сделайте один проход через список чисел. Псевдокод:
bestIndex = 0 bestLength = 0 curIndex = 0 curLength = 1 for index = 1..length-1 if a[index] is less than or equal to a[index-1] curLength++ else //restart at this index since it's a new possible starting point curLength = 1 curIndex = index if curLength is better than bestLength bestIndex = curIndex bestLength = curLength next
Примечание: Вы можете удалить любую строку, содержащую bestIndex или curIndex, если вам не нужно знать, где происходит эта подпоследовательность, как показано в реализации Гэри.
Другая реализация в python:
def longest_down_sequence(seq): max = 0 current_count = 0 last = None for x in seq: if x <= last: current_count += 1 else: current_count = 1 if current_count > max: max = current_count last = x return max
В java:
int [] myArray = {5,-11,2,3,14,5,-14,2}; int downSequence = 1; int longestDownSequence = 1; for(int i = 1; i < myArray.length; i++) { if(myArray[i] <= myArray[i-1]) downSequence++; else { if(downSequence > longestDownSequence) longestDownSequence = downSequence; downSequence = 1; } } if(downSequence > longestDownSequence) longestDownSequence = downSequence; System.out.println(longestDownSequence);
Поскольку вы просите самую быструю или лучшую производительность, проверьте только самую длинную последовательность вниз непосредственно перед сбросом счетчика. Никогда на каждой итерации. Тем не менее, вы должны проверить снова после цикла в случае, если самая длинная последовательность находится в конце массива.
Другое решение в Java:
static int[] longestDownSequenceList(int[] array) { if (array.length <= 1) { return array; } int maxSize = 1; int maxEnd = 0; int curSize = 1; for (int i = 1; i < array.length; i++) { if (array[i] < array[i-1]) { curSize++; if (curSize > maxSize) { maxSize = curSize; maxEnd = i; } } else { curSize = 1; } } return Arrays.copyOfRange(array, maxEnd-maxSize+1, maxEnd+1); }
Как сказал Билл выше, это по существу самая длинная возрастающая подпоследовательность. Смотрите статью Википедии для оптимального решения. Это цитируется оттуда с небольшими изменениями, чтобы работать для случая неубывания
См. контрпример к другому предложенному решению в моем комментарии выше.L = 0 for i = 1, 2, ... n: binary search for the largest positive j ≤ L such that X[M[j]] >= X[i] (or set j = 0 if no such value exists) P[i] = M[j] if j == L or X[i] >= X[M[j+1]]: M[j+1] = i L = max(L, j+1)
Самый быстрый способ может зависеть от среды: компьютера и размера проблемы.
Для очень большого списка (или массива) может быть полезно распараллелить задание, которое может быть реализовано:
- разбить и разбить список на простые элементы.
- склейте вместе элементы, которые являются понижающими последовательностями (или не увеличивающимися) в куски, и склейте вместе куски, если это возможно.
- Найдите самый длинный кусок.