Longest contiguous Increasing Subset in java

Question

I have tried to come up with a solution to the longest increasing subsequence problem.Can this solution be optimized further?

Example 1:

• Input: {5,4,3,7,8,9,11}
• Output: 3, 7, 8, 9, 11

Example 2:

• Input: {1,2,1,2,1}
• Output: 1, 2 (the latest one)

Implementation:

 public class LongestIncreasingSubsequence {
 public static ArrayList<Integer>[] getLongestIncreasingSubsequence(int[] array, ArrayList<Integer>[] list,
 int index) {
 list[index] = new ArrayList<Integer>();
 if (index == 0) {
 list[index].add(array[index]);
 }
 else {
 if (array[index] > array[index - 1]) {
 list[index].addAll(list[index - 1]);
 }
 list[index].add(array[index]);
 }
 if (index == array.length - 1)
 return list;
 return getLongestIncreasingSubsequence(array, list, index + 1);
 }
 public static List<Integer> findLIS(int[] array) {
 ArrayList<Integer>[] arrayList = getLongestIncreasingSubsequence(array, new ArrayList[array.length], 0);
 int maxLength = arrayList[array.length - 1].size();
 int maxIndex = array.length - 1;
 for (int i = array.length - 2; i >= 0; i--) {
 if (arrayList[i].size() > maxLength) {
 maxLength = arrayList[i].size();
 maxIndex = i;
 }
 }
 return arrayList[maxIndex];
 }
 public static void main(String args[]) {
 int[] array = new int[] { 7, 1, 3, 8, 11 };
 List<Integer> LIS = findLIS(array);
 for (Integer i : LIS)
 System.out.print(i + ",");
 }
 }

Answer 1

For an input array of N values, the current implementation creates N instances of ArrayList. But you only need 2:

• One to store the longest sequence seen so far
• One to store the currently tracking sequence

For example the input 5, 6, 7, 1, 2, 3, 4, walking through the elements from the start:

• 5: the first element -> add it to the current sequence
• 6: greater than the previous -> add it to the current sequence
• 7: greater than the previous -> add it to the current sequence
• 1: the current sequence is broken -> the current sequence is longer than the longest sequence -> update the longest sequence = [5, 6, 7]
• 2: greater than the previous -> add it to the current sequence
• 3: greater than the previous -> add it to the current sequence
• 4: greater than the previous -> add it to the current sequence
• Reached the end -> the current sequence is longer than the longest sequence -> the longest sequence is [1, 2, 3, 4]

The implementation can be simplified to:

public static List<Integer> findLIS(int[] array) {
 List<Integer> longest = new ArrayList<>();
 List<Integer> current = new ArrayList<>();
 int previous = Integer.MAX_VALUE;
 for (int value : array) {
 if (value <= previous) {
 if (longest.size() < current.size()) {
 longest = current;
 }
 current = new ArrayList<>();
 }
 current.add(value);
 previous = value;
 }
 return longest.size() < current.size() ? current : longest;
}

Some other tips on the original code:

• Avoid arrays of generic types such as ArrayList<Integer>[]
• Prefer interface types in declarations and method return types, such as List instead of ArrayList
• When initializing generic types, Java 7 can guess the correct type parameter, so instead of new ArrayList<Integer>() you can write new ArrayList<>() (also known as the diamond operator <>)
• The indentation and formatting was inconsistent, use an IDE to format the code nicely
• Instead of printing elements of LIS one by one, System.out.println(LIS) would easily produce an output that's just as readable
• A more compact writing style to initialize an array: int[] array = { 7, 1, 3, 8, 11 };

• DontForgetTheSemiColon: Thank you very much! never thought i need only two lists :)