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;
}

今天发现服务器上的一个sql执行非常慢，两张关联表查询

有一张关注表user_focus，和一张关注备注表user_focus_note

sql如下：

select t1.FLYID,t1.FLYKEY,t1.ISPUSH,t1.NOTIFYSTATE,t2.description,t2.remind_times from USER_FOCUS t1 left join USER_FOCUS_note t2 on t1.ID=t2.user_focus_id where (t1.USERID=’1378416183′ or t1.PHONEID=’18820063′) and t1.ORDERTYPE=’0′ and t1.NOTIFYSTATE=’0′ and t1.UPDATETIME >= ’2016-09-24 00:00:00′ UNION select t3.FLYID,t3.FLYKEY,t3.ISPUSH,t3.NOTIFYSTATE,t4.description,t4.remind_times from USER_FOCUS t3 left join USER_FOCUS_note t4 on t3.ID=t4.user_focus_id where (t3.USERID=’1378416183′ or t3.PHONEID=’18820063′) and t3.ORDERTYPE=’0′ and t3.NOTIFYSTATE in (1,2) and t3.UPDATETIME >= ’2016-10-24 09:55:19′;

进一步分析，发现下面sql执行很慢，基本上再20s以上，但返回结果只有1000多条

select t1.FLYID,t1.FLYKEY,t1.ISPUSH,t1.NOTIFYSTATE,t2.description,t2.remind_times from USER_FOCUS t1 left join USER_FOCUS_NOTE t2 on t1.ID=t2.user_focus_id where (t1.USERID=’1378416183′ or t1.PHONEID=’18820063′) and t1.ORDERTYPE=’0′ and t1.NOTIFYSTATE=’0′ and t1.UPDATETIME >= ’2016-09-24 00:00:00′

其中user_focus有1600万条数据，PHONEID，USERID，UPDATETIME 都建了索引，

去掉关联查询后，速度一下子就提升上来了，基本100ms就执行完了，所以确定是使用left join的问题，查看了下user_focus_note表，发现有18w条数据，数据量不大啊，怎么回事？

仔细查看了sql，这里有用到t1.ID=t2.user_focus_id，USER_FOCUS_NOTE 表user_focus_id建立了一个索引，重新执行sql，速度果然很快。USER_FOCUS 表虽然只有1000多条数据满足，但是查询USER_FOCUS_NOTE表时都需要扫描全表，这样就有180000*1000条扫描，所以查询肯定很慢

总结：类似两个大表，或一个大表、一个小表做关联查询时，一定要建立好索引。