HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Finding the longest sequence of increasing numbers in an array

Submitted by: @import:stackexchange-codereview··
0
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 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 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.