HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Find the longest sequence of increasing numbers in an array

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thearraynumberssequenceincreasingfindlongest

Problem

I have the following task: to find the largest sequence of increasing numbers in an array.

I'll give you an example : 2 3 4 1 50 2 3 4 5 will return the sequence of 2 3 4 5 - that is the largest sequence of increasing numbers in the given array.
Another one is : 5 -1 10 20 3 4 which will return -1 10 20.

If there are two equal sequences -for example 4 5 1 2 -1 which has the sequences 4 5 and 1 2 the first sequence will be returned.

Below is my method

public static List findLongestIncreasingSequence(int[] numbersToBeProcessed) {

        List longestIncreasingSequence = new ArrayList();
        List currentNumbersSequence = new ArrayList();

        for (int i = 0; i = nextNumber || i == numbersToBeProcessed.length - 1) {
                // checks if the current sequence is bigger
                if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
                    longestIncreasingSequence.clear();
                    longestIncreasingSequence.addAll(currentNumbersSequence);
                }
                //clear the current sequence so it can start all over again
                currentNumbersSequence.clear();
            }
        }

        return longestIncreasingSequence;
    }


Any feedback received on this method is more than welcome. The thing I dislike the most is the check I make for the last element in order to avoid ArrayIndexOutOfBounds exception.

Solution

The thing I dislike the most is the check I make for the last element in order to avoid ArrayIndexOutOfBounds exception.

So let's avoid that check. Let's structure our loop such that we're back-comparing. That is, instead of comparing index i to index i+1, we compare index i to index i-1. That way, if we start at 1, we'll always have a valid comparison - since otherwise our loop invariant would've triggered:

for (int i = 1; i  vals[i-1]) {
        // continuing this sequence
    }
    else {
        // start a new sequence, of length 1, from i
    }
}


No further checks against vals.length are necessary, once we handle the empty case. The rest of the algorithm involves just keeping track of a current running sequence and the best sequence so far, which you could do with a local ArrayList but better to just do with a couple ints.

Code Snippets

for (int i = 1; i < vals.length; ++i) {
    if (vals[i] > vals[i-1]) {
        // continuing this sequence
    }
    else {
        // start a new sequence, of length 1, from i
    }
}

Context

StackExchange Code Review Q#110487, answer score: 4

Revisions (0)

No revisions yet.