Finding the longest sequence in a Java array

Question

Given this array

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

I should be able to return 3 because the longest bottom sequence is 14.5, -14. What is the fastest way to do this?

PS: The bottom sequence is a series of non-decreasing numbers.

Answer 1

Just make one pass through the list of numbers. Pseudocode:

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 a new possible starting point
       curLength = 1
       curIndex = index

   if curLength is better than bestLength
       bestIndex = curIndex
       bestLength = curLength

next          

Note. You can cut any string containing bestIndex or curIndex if you are not interested in knowing where this subsequence occurs, as can be seen from the Gary implementation.

Answer 2

another python implementation:

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

, , reset . . , , .

Answer 4

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 5

, , , . . 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)

. counterexample .

Answer 6

: .

For a very large list (or array) it may be useful to parallelize the task, which can be implemented:

• Split and split and split the list into simple elements.
• Glue elements that are descending sequences (or do not increase) to pieces, and stick pieces if possible.
• Find the longest piece.