Find the longest ascending subarray from a given array

Question

I have following task, form a given array, I want the longest ascending array. I will give you an example

int[] a = {19,12,13,1,2,3,4,5,14,23,24,25,26,31,32};

will return array of {1,2,3,4,5} - that is the largest sequence of ascending numbers in the given array.

Below is the sample code:

int[] a = {19,12,13,1,2,3,4,5,14,23,24,25,26,27,31,32};
        List<Integer> longestArray = new ArrayList<Integer>();
        List<Integer> currentArary = new ArrayList<Integer>();              
        for (int i = 1; i < a.length; i++) {
            if(currentArary.isEmpty()) {
                currentArary.add(a[i-1]);
            }
            if (a[i]-1 == a[i-1]) {
                currentArary.add(a[i]);
            } else {
                if(longestArray.size()<currentArary.size()) {
                    longestArray.clear();
                    longestArray.addAll(currentArary);
                }
                currentArary.clear();
            }
        }
        System.out.println(longestArray);

Any feedback received on this method is more than welcome.

Answer 1

Josay provided a lot of good feedback, so I'll try to focus on something I think is very important.

There's no need to save the current subsequence

For your solution, you manage two lists, both of which are rewritten and cleared multiple times. Instead of doing this, we can just save where the largest subsequence starts, and how long it is. This can be stored in two integers.

When looping, we also keep track of where the current subsequence started, and how long it is. Once it is broken, we simply compare the length to the previous maximum length, and update accordingly. I also added a check to handle sequences which are fully ascending (e.g. {1, 2, 3, 4, 5}).

public static int[] getLongestAscending(int[] a) {
    int maxLength = 0;
    int maxStart = 0;
    int length = 1;
    int start = 0;
    boolean fullAscension = true;
    for (int i = 1; i < a.length; i++) {
        if (a[i]-1 == a[i-1]) {
            length++;
        } else {
            fullAscension = false;
            if (length > maxLength) {
                maxLength = length;
                maxStart = start;
            }
            length = 1;
            start = i;
        }
    }
    if (fullAscension) {
        return a;
    }
    if (length > maxLength) {
        maxLength = length;
        maxStart = start;
    }       int[] ret = new int[maxLength];
    System.arraycopy(a, maxStart, ret, 0, maxLength);
    return ret;
}

According to me, this is clearer, and saves all information needed. It also has the advantage of returning data on the same format as the input, and it is also quite a bit faster. From some benchmarks it seems to be about 20-30 times faster.

Answer 2

Variable names/typos

In 7 places, you've written Arary instead of Array. A single simple review of your own code should have caught that.

Separation of concerns/testability

Instead of having a function with the a value hard-coded, you could pass it as a parameter.

Instead of having the computed value printed to standard-output, you could have it returned by the function.

Then, your code is better organised: you have a function with a single-responsability (getting the longest ascending subarray), not dealding with other concerns such as input/output from the user. Among other things, the code is also easier to test now.

I still have to write the proper tests but for the time being, we have:

import java.util.*;

public class ascendingArray {
    public static List<Integer> getLongestAscendingSubarray(int[] a) {
        List<Integer> longestArray = new ArrayList<Integer>();
        List<Integer> currentArray = new ArrayList<Integer>();
        for (int i = 1; i < a.length; i++) {
            if(currentArray.isEmpty()) {
                currentArray.add(a[i-1]);
            }
            if (a[i]-1 == a[i-1]) {
                currentArray.add(a[i]);
            } else {
                if(longestArray.size()<currentArray.size()) {
                    longestArray.clear();
                    longestArray.addAll(currentArray);
                }
                currentArray.clear();
            }
        }
        return longestArray;
    }

    public static void main(String[] args) {
        System.out.println("Hello, world!");
        int[] a = {19,12,13,1,2,3,4,5,14,23,24,25,26,27,31,32};
        System.out.println(getLongestAscendingSubarray(a));
    }
}

Answer 3

Your currentArary [sic] shouldn't ever be empty. You should initialize it with a[0], and from then on, if a[i] is not equal to a[i-1]+1, then you should set currentArary to a[i]. Waiting until the next iteration, and then putting what is now a[i-i] into the array, is needlessly opaque.

But since you're looking for consecutive integers, you don't need to store a copy of a subset of a at all; it's fully determined by the start element and the length.

public static int[] getLongestAscending(int[] a) {
    int maxLength = 1;
    int maxStart = a[0];
    int curLength = 1;
    int curStart = a[0];
    for (int i = 1; i < a.length; i++) {
        if ((a[i] != a[i-1]+1)||(i == a.length-1) {
            if (curLength > maxLength) {
                maxLength = curLength;
                maxStart = curStart;
            }
            curLength = 1;
            curStart = a[i];
        } else {
            curLength++;
        }
    }
    return int[] array = IntStream.range(maxStart, maxStart+maxLength).toArray();
}