CODEWITHSUNDEEP
javaarraysalgorithmsequence
Derek Long
Derek Long

Reputation: 1219

Finding the longest down sequence in a Java array

Given this array 

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

I must be able to return 3 because the longest down sequence is 14,5,-14. What's the fastest way to do this?

PS: Down sequence is a series of non-increasing numbers.

Upvotes: 3

Views: 4883

Answers (6)

jfajunior
jfajunior

Reputation: 1251

Another solution in 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);
}

Upvotes: 1

user unknown
user unknown

Reputation: 36229

The fastest way might depend on the environment: computer and problemsize.

For a very large List (or array) it might be useful to parallelize the job, which could be implemented:

  • Split and split and split the List to simple elements.
  • Glue together elements which are down sequences (or non increasing) to chunks, and glue together chunks, if possible.
  • Search for the longest chunk.

Upvotes: 0

gtrak
gtrak

Reputation: 5676

another implementation in 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

Upvotes: 3

Adrian M
Adrian M

Reputation: 7435

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

Since you're asking for fastest or better performance, only check for the longest down sequence just before you reset the counter. Never on each iteration. However, you have to check again after the loop in case the longest sequence is at the end of the array.

Upvotes: 1

piccolbo
piccolbo

Reputation: 1315

As Bill above said, this is essentially longest increasing subsequence. See the wikipedia entry for the optimal solution. This is quoted from there with small changes to work for the nondecreasing case

 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)

See counterexample to other proposed solution in my comment above.

Upvotes: 0

Mark Peters
Mark Peters

Reputation: 81074

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

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

next

Note: You can ditch any line containing bestIndex or curIndex if you don't care about knowing where that subsequence occurs, as seen in Gary's implementation.

Upvotes: 2

Related Questions