Finding the longest sequence of increasing numbers in an array

Question

A continuation of this queston. The task's description can also be found there.

After reformatting the code and getting rid of the ArrayIndexOutOfBounds check,it now looks like this:

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {
 if (numbersToBeProcessed.length == 0) {
 return null;
 }
 List<Integer> longestIncreasingSequence = new ArrayList<Integer>();
 List<Integer> currentNumbersSequence = new ArrayList<Integer>();
 // the first number will be added always,no matter what
 currentNumbersSequence.add(numbersToBeProcessed[0]);
 for (int i = 1; i < numbersToBeProcessed.length; i++) {
 int currentNumber = numbersToBeProcessed[i];
 int previousNumber = numbersToBeProcessed[i - 1];
 if (currentNumber > previousNumber) {
 currentNumbersSequence.add(currentNumber);
 } else {
 // 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();
 // after clearing add the current number as the first of the new
 // sequence
 currentNumbersSequence.add(currentNumber);
 }
 }
 // at the end of the loop always compare the two sequences.
 if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
 longestIncreasingSequence.clear();
 longestIncreasingSequence.addAll(currentNumbersSequence);
 }
 return longestIncreasingSequence;
 }

There are couple of things that bother me about the algorithm above:

1. We never actually check the n-1 number at the start of the algorithm - instead we directly check if the n number and we process it. This is why I have added the currentNumbersSequence.add(numbersToBeProcessed[0]); code line before we go in the for loop.

2. What if the last n number is bigger than n-1? That means that we do not go into the else statement and the current sequence will never be compared against the largest one at this moment. This is why I had to add an extra check after the for loop. However it leads to a very obvious code repetition.

Answer 1

No need for temporary lists

In your last review, it was mentioned that you could just use two integers to keep track of the sequences instead of two whole lists. So instead of currentNumbersSequence and longestIncreasingSequence, you could track just the start and length of those two sequences. The code then becomes:

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {
 if (numbersToBeProcessed.length == 0) {
 return null;
 }
 int bestStart = 0;
 int curStart = 0;
 int bestLength = 1;
 int curLength = 1;
 for (int i = 1; i < numbersToBeProcessed.length; i++) {
 if (numbersToBeProcessed[i] > numbersToBeProcessed[i-1]) {
 curLength++;
 if (curLength > bestLength) {
 bestStart = curStart;
 bestLength = curLength;
 }
 } else {
 curStart = i;
 curLength = 1;
 }
 }
 ArrayList<Integer> ret = new ArrayList<>(bestLength);
 for (int i = 0; i < bestLength; i++) {
 ret.add(numbersToBeProcessed[bestStart+i]);
 }
 return ret;
}

• Gentian Kasa: Performance wise this is the best approach. One thing I noticed is that it may not be strictly necessary to return a List<Integer> (but it depends on a lot of other things) and a int[] should be enough. In this case the for loop could be replaced by a System.arraycopy() (if I remember correctly). Anyway, +1 :)
• Bruno Costa: You can check if there aren't enough elements left to replace your current best sequence. something like ths if(bestLength >= numbersToBeProcessed.length - currStart) break; on the else statement. Please remember to do some unit testing with this :p.
• JS1: @GentianKasa Yes returning a int[] is better. I only used an List because your function returned one and I didn't know if that was a requirement.
• Gentian Kasa: I used a List for the same reasons actually :). The int[] idea popped up in my mind only when i saw your solution (and I personally find it more logical actually, I mean, a List is actually something meant to be "dynamic", while the method just needs to return something "static", but that's just my opinion on the matter).

Answer 2

You actually have to pieces of code that are repeated:

if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
 longestIncreasingSequence.clear();
 longestIncreasingSequence.addAll(currentNumbersSequence);
}

and

currentNumbersSequence.add(currentNumber);

The former should be extracted and put into a method or just return the longest sequence if you're out of the loop (and this takes care of your concern #2). The latter can just be taken out of the if condition. The code inside the for loop can be written as follows:

 int currentNumber = numbersToBeProcessed[i];
 int previousNumber = numbersToBeProcessed[i - 1];
 if (currentNumber <= previousNumber) {
 // replace this piece with the call to the method that I suggested previously
 if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
 longestIncreasingSequence.clear();
 longestIncreasingSequence.addAll(currentNumbersSequence);
 }
 currentNumbersSequence.clear();
 }
 currentNumbersSequence.add(currentNumber);

For you 1st concern you could change your for loop into the following:

 for (int i = 0; i < numbersToBeProcessed.length - 1; i++) {
 int currentNumber = numbersToBeProcessed[i + 1];
 int previousNumber = numbersToBeProcessed[i];
 currentNumbersSequence.add(previousNumber);
 // rest of the code
 // you should also remove the 'currentNumbersSequence.add(currentNumber);' line
 }

This change allows you to remove the currentNumbersSequence.add(numbersToBeProcessed[0]); line.

So, in short, the method should become something like the following (not tested):

public static List<Integer> findLongestIncreasingSequence(int[] numbersToBeProcessed) {
 if (numbersToBeProcessed.length == 0) {
 return null;
 }
 List<Integer> longestIncreasingSequence = new ArrayList<Integer>();
 List<Integer> currentNumbersSequence = new ArrayList<Integer>();
 for (int i = 0; i < numbersToBeProcessed.length - 1; i++) {
 int currentNumber = numbersToBeProcessed[i];
 int previousNumber = numbersToBeProcessed[i - 1];
 currentNumbersSequence.add(previousNumber);
 if (currentNumber <= previousNumber) {
 // 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();
 }
 }
 // at the end of the loop always compare the two sequences.
 if (currentNumbersSequence.size() > longestIncreasingSequence.size()) {
 return currentNumbersSequence;
 }
 return longestIncreasingSequence;
}