Нахождение самой длинной последовательности вниз в массиве Java

Question

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

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

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

PS: Последовательность понижений - это серия не увеличивающихся чисел.

Answer 1

другая реализация в 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

Answer 2

Просто сделайте один проход по списку номеров. Псевдокод:

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, если вам не нужно знать, где происходит эта подпоследовательность, как видно из реализации Гэри.

Answer 3

Другое решение в 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);
}

Answer 4

В 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);

Поскольку вы запрашиваете максимальную или лучшую производительность, проверяйте только самую длинную последовательность понижений непосредственно перед сбросом счетчика.Никогда на каждой итерации.Тем не менее, вы должны проверить еще раз после цикла, если самая длинная последовательность находится в конце массива.

Answer 5

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

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

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

Answer 6

Как сказал Билл выше, это по сути самая длинная возрастающая подпоследовательность.Смотрите статью в Википедии для оптимального решения.Это цитируется там с небольшими изменениями в работе для неубывающего случая

 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)

См. Контрпример к другому предложенному решению в моем комментарии выше.