Найти самую длинную последовательность в массив Java


Учитывая этот массив

int [] myArray = {5,-11,2,3,14,5,-14,2};

Я должен быть в состоянии вернуть 3, потому что самая длинная нисходящая последовательность-14,5, -14. Какой самый быстрый способ сделать это?

ЗЫ: последовательность-это серия не увеличивается.

6 3

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)
См. контрпример к другому предложенному решению в моем комментарии выше.

Самый быстрый способ может зависеть от среды: компьютера и размера проблемы.

Для очень большого списка (или массива) может быть полезно распараллелить задание, которое может быть реализовано:

  • разбить и разбить список на простые элементы.
  • склейте вместе элементы, которые являются понижающими последовательностями (или не увеличивающимися) в куски, и склейте вместе куски, если это возможно.
  • Найдите самый длинный кусок.