patternjavaMinor
Find the longest sequence of increasing numbers in an array
Viewed 0 times
thearraynumberssequenceincreasingfindlongest
Problem
I have the following task: to find the largest sequence of increasing numbers in an array.
I'll give you an example :
Another one is :
If there are two equal sequences -for example
Below is my method
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
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 findLongestIncreasingSequence(int[] numbersToBeProcessed) {
List longestIncreasingSequence = new ArrayList();
List currentNumbersSequence = new ArrayList();
for (int i = 0; i = 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.Solution
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
No further checks against
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[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 but better to just do with a couple ints.Code Snippets
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
}
}Context
StackExchange Code Review Q#110487, answer score: 4
Revisions (0)
No revisions yet.