Longest contiguous Increasing Subset in java 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&lt;Integer&gt;[] getLongestIncreasingSubsequence(int[] array, ArrayList&lt;Integer&gt;[] list,
                int index) {

            list[index] = new ArrayList&lt;Integer&gt;();

            if (index == 0) {
                list[index].add(array[index]);

            }

            else {

                if (array[index] &gt; 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&lt;Integer&gt; findLIS(int[] array) {

            ArrayList&lt;Integer&gt;[] 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 &gt;= 0; i--) {
                if (arrayList[i].size() &gt; 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&lt;Integer&gt; LIS = findLIS(array);

            for (Integer i : LIS)
                System.out.print(i + ",");

        }
    }
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&lt;Integer&gt; findLIS(int[] array) {
    List&lt;Integer&gt; longest = new ArrayList&lt;&gt;();
    List&lt;Integer&gt; current = new ArrayList&lt;&gt;();

    int previous = Integer.MAX_VALUE;
    for (int value : array) {
        if (value &lt;= previous) {
            if (longest.size() &lt; current.size()) {
                longest = current;
            }
            current = new ArrayList&lt;&gt;();
        }
        current.add(value);
        previous = value;
    }

    return longest.size() &lt; current.size() ? current : longest;
}


Some other tips on the original code:


Avoid arrays of generic types such as ArrayList&lt;Integer&gt;[]
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&lt;Integer&gt;() you can write new ArrayList&lt;&gt;() (also known as the diamond operator &lt;&gt;)
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 };