4
\$\begingroup\$

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.

\$\endgroup\$
2

1 Answer 1

4
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.