题解 | #最长递增子序列#

nums数组保存第i个数在该数组中的的最长递增子序列长度
temp数组用来辅助确认第i个数在该数组中的最长递增子序列长度
tempIdx用来从后往前遍历temp数组，确认第i个数在该数组中的最长递增子序列长度
tempMax用来最长递增子序列的长度
max用来保存最长递增子序列最后一个数的位置

遍历逻辑：
for循环遍历每一个数
while循环用于寻找当前第i个数在数组中的位置，注意while循环结束后tempIdx需要+1
更新tempMax和max
更新temp和nums的值
最后注意把tempMax赋值给tempIdx以便下一个数的while循环继续遍历

返回数组：
首先tempMax保存了最长递增子序列的长度，但是由于数组从0开始算，所以创建res时长度为tempMax+1
然后从max位置开始从后往前遍历，每找到==tempMax的数就赋值给res[tempMax]，把tempMax减一

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        int[] nums = new int[arr.length];
        int[] temp = new int[arr.length];
        nums[0] = 0;
        temp[0] = arr[0];
        int tempIdx = 0;
        int tempMax = 0;
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            while (tempIdx >= 0 && arr[i] <= temp[tempIdx]) {
                tempIdx--;
            }
            tempIdx++;
            if (tempIdx >= tempMax) {
                tempMax = tempIdx;
                max = i;
            }
            temp[tempIdx] = arr[i];
            nums[i] = tempIdx;
            tempIdx = tempMax;
        }
        int[] res = new int[tempMax + 1];
        for (int i = max; i >= 0; --i) {
            if (nums[i] == tempMax) {
                res[tempMax] = arr[i];
                --tempMax;
            }
        }
        return res;
    }
}