# Find the longest sequence of increasing numbers in an array

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

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];
}
//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
longestIncreasingSequence.clear();
}
//clear the current sequence so it can start all over again
}
}

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.

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.

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