patternjavaMinor
Finding the longest sequence of increasing numbers in an array
Viewed 0 times
thearraynumberssequenceincreasingfindinglongest
Problem
A continuation of this queston.
The task's description can also be found there.
After reformatting the code and getting rid of the
There are couple of things that bother me about the algorithm above:
-
We never actually check the
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 findLongestIncreasingSequence(int[] numbersToBeProcessed) {
if (numbersToBeProcessed.length == 0) {
return null;
}
List longestIncreasingSequence = new ArrayList();
List currentNumbersSequence = new ArrayList();
// the first number will be added always,no matter what
currentNumbersSequence.add(numbersToBeProcessed[0]);
for (int i = 1; i 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:
-
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.Solution
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
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 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[i-1]) {
curLength++;
if (curLength > bestLength) {
bestStart = curStart;
bestLength = curLength;
}
} else {
curStart = i;
curLength = 1;
}
}
ArrayList ret = new ArrayList<>(bestLength);
for (int i = 0; i < bestLength; i++) {
ret.add(numbersToBeProcessed[bestStart+i]);
}
return ret;
}Code Snippets
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;
}Context
StackExchange Code Review Q#110497, answer score: 6
Revisions (0)
No revisions yet.