Longest Increasing Subsequence (LIS)

/*  Read a list of integers and find the longest increasing subsequence (LIS). If several such exist, print the leftmost.
*   Hints:
*   • Assume we have n numbers in an array numbers[0…n-1].
*   • Let lengthArr[p] holds the length of the longest increasing subsequence (LIS) ending at position p.
*   • In a for loop, we shall calculate length[p] for p = 0 … n-1 as follows:
*         Let left is the leftmost position on the left of p (left < p), such that lengthArr[left] is the largest possible.
*         Then, lengthArr[p] = 1 + lengthArr[left]. If left does not exist, lengthArr[p] = 1.
*         Also, save prevIndxArr[p] = left (we hold if prevIndxArr[] the previous position, used to obtain the best length for position p).
*       Once the values for lengthArr[0…n-1] are calculated, restore the LIS starting from position p such that lengthArr[p] is maximal
*       and go back and back through p = prevIndxArr[p].
*
*        Examples:
*    [1]  ->   [1];   [7 3 5 8 -1 0 6 7]   ->   [3 5 6 7];     [1 2 5 3 5 2 4 1]   ->    [1 2 3 5];
*    [0 10 20 30 30 40 1 50 2 3 4 5 6]   ->   [0 1 2 3 4 5 6];    [3 14 5 12 15 7 8 9 11 10 1]   ->   [3 5 7 8 9 11];
*    [11 12 13 3 14 4 15 5 6 7 8 7 16 9 8]   ->   [3 4 5 6 7 8 16];     [7 7 7]   ->   [7];
*/


import java.util.Arrays;
import java.util.Scanner;

public class LIS {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split("\\s+");
        scanner.close();

        int[] numbers = Arrays.stream(arr)
                .mapToInt(Integer::parseInt)
                .toArray();

        int[] lengthArr = new int[numbers.length];
        int[] prevIndxArr = new int[numbers.length];
        int maxLength = 0;
        int lastIndex = -1;
        for (int i = 0; i < numbers.length; i++) {
            lengthArr[i] = 1;
            prevIndxArr[i] = -1;
            for (int j = 0; j < i; j++) {
                if ((numbers[j] < numbers[i]) && (lengthArr[j] + 1 > lengthArr[i])) {
                    lengthArr[i] = lengthArr[j] + 1;
                    prevIndxArr[i] = j;
                }

            }

            if (lengthArr[i] > maxLength) {
                maxLength = lengthArr[i];
                lastIndex = i;
            }
        }

        int[] longestSeq = new int[maxLength];
        for (int i = maxLength - 1; i >= 0; i--) {
            longestSeq[i] = numbers[lastIndex];
            lastIndex = prevIndxArr[lastIndex];
        }

        for (int num : longestSeq) {
            System.out.printf("%d ", num);
        }
    }
}