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

Question

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

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

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

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

Answer 1

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

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 2

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

В 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 4

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

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) 

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

Answer 5

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

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

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

Answer 6

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