LIS算法又称最长公共子序列，即找出一组数中最长的子序列，比如我们可以用于判断一个物体是在上升还是下降

如何判断物体是在上升还是下降，单纯用末尾数字-首位数字，可能结果并不准确，因为物体可能是一个抖动形的移动趋势。

我们的航班系统会实时收集飞机的坐标，比如在飞机起飞/降落的时候收集它的坐标位置，因为飞机的起飞或降落不是呈现高度递增或递减的，很有可能是先上升了一段高度，由于气流的原因又下降了一段距离再上升

比如一个我们收集了飞机一段高度数据为：{ 2000, 3125, 3325, 2000, 3325, 4025, 4575, 5625, 6900, 7925, 7950, 7925, 7700, 7275, 7050, 6925, 6500, 6350, 5400, 4825, 3150, 2250 }

使用LIS算法正序求得：{2000 2250 3150 4025 4575 4825 6350 6925 7950 },

逆序求得：{2000 3125 3325 5400 5625 6500 6900 7050 7275 7700 7925 7950}

我们从结果中分析逆序LTS更长，表明飞机是在下降的趋势。

实现源码

public static int[] longestIncreasingSubsequence(int[] arr) {
    int i, n = arr.length, top, temp;
    int[] stack = new int[n + 1];
    int[] idxes = new int[n];
    top = 0;
    int idx = 0;// 记录LIS序列中元素对应的arr下标，便于修正LIS中下标错位的元素

    /* 为了方便top始终指向栈顶，stack从下标1开始使用，stack[0]设置为-1不使用 */
    stack[0] = -1;

    // -----------------------------------
    // 一个for循环加一个二分查找，算法时间复杂度是o(NlogN)
    // -----------------------------------
    for (i = 0; i < n; i++) {
        temp = arr[i];
        /* 比栈顶元素大数就入栈 */
        if (temp > stack[top]) {
            stack[++top] = temp;
            idxes[idx++] = i;
        } else {
            int low = 1, high = top;
            int mid;
            /* 二分检索栈中比temp大的第一个数 */
            while (low <= high) {
                mid = (low + high) / 2;
                if (temp > stack[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            /* 用temp替换 */
            stack[low] = temp;
            idxes[low - 1] = i;
        }
    }

    print(idxes);
    int[] lis = Arrays.copyOfRange(stack, 1, top + 1);
    print(lis); // 得到递增的最长子序列，但不一定是原数组的最长上升子序列

    return lis;
}