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.

• Vogel612: Barry has rolled back the last edit. Please see what you may and may not do after receiving answers .
• pgerchev: I have posted a follow-up question here

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.

• pgerchev: could you please have a look at the original post that I have updated after your remarks?
• Barry: @pgerchev Code should not be updated in questions, I've reverted your changes.