Find the longest sequence of increasing numbers in an array

Question

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<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {

        List<Integer> longestIncreasingSequence = new ArrayList<Integer>();
        List<Integer> currentNumbersSequence = new ArrayList<Integer>();

        for (int i = 0; i < numbersToBeProcessed.length; i++) {

            int currentNumber = numbersToBeProcessed[i];
            int nextNumber = 0;

            // checks if it is not the last number in the array
            if (i != numbersToBeProcessed.length - 1) {
                nextNumber = numbersToBeProcessed[i + 1];
            }
            currentNumbersSequence.add(currentNumber);
            //checks if the current sequence ends here(the next number is smaller or equal)
            //or if the array ends
            if (currentNumber >= 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.

Answer 1

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.length; ++i) {
    if (vals[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<Integer> but better to just do with a couple ints.