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.

• 301_Moved_Permanently: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Acccumulation: You appear to be wanting the longest sequence of consecutively increasing numbers. The longest ascending sequence is {1,2,3,4,5,14,23,24,25,26,31,32}. Although, as @MathiasEttinger said, you shouldn't update your code, I think you should edit your question to make this clearer.
• Acccumulation: Is there a reason for doing longestArray.clear(); longestArray.addAll(currentArary) rather than longestArray = currentArary?

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.

• Errorsatz: Small fix - you need to repeat the length > maxLength check after the for loop ends; otherwise a sequence like "6,7,1,2,3,4,5" will return "6,7".
• maxb: @Errorsatz good catch! I'll update the code.

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));
 }
}

• maxb: One bug I found is that this solution returns an empty list for a sequence which is strictly ascending. Try {1, 2, 3, 4, 5} as input.
• SylvainD: This is definitly worth an answer on its own.

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();
}

• yuri: should ever be empty Did you mean never?