题解 | #数组中的最长连续子序列#

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     * 
     * 将序列排成递增序列。然后遍历数组，依次将其与前一个数比较，若是比前一个大1，
     * 则连续子序列增加1；若是与前一个一样大，需要不管直接进入下一循环（去重）；
     * 若是比前一个大超过1，则连续断掉，重新计数，同时比较并更新最大值。
     */
    public int MLS (int[] arr) {

        if (arr == null) {
            return 0;
        }

        if (arr.length == 1) {
            return 1;
        }

        /**
          * 复杂度分析：
          * 时间复杂度：O(ngln)，快速排序的时间复杂度
          * 空间复杂度：O(1)，没有额外空间
          */
        quickSort(0, arr.length - 1, arr);

        int max = 1;

        int tempMax = 1;

        for (int i = 1; i < arr.length; i++) {//逐一比较该数与前一个数

            if (arr[i] == arr[i-1] + 1) {
                tempMax++;
            } else if (arr[i] == arr[i-1]) {//重复元素情况 若是相等，则跳过
                continue;
            } else {
                tempMax = 1;
            }

            max = Math.max(tempMax, max);//防止最后一个数字重复，跳过了上面的最大值比较
        }

        return max;
    }

    public void quickSort (int start, int end, int[] arr) {

        if (start > end) {
            return;
        }

        int left = start;
        int right = end;
        int target = arr[start];

        while (left < right) {

            while (left < right && arr[right] >= target) {
                right--;
            }

            while (left < right && arr[left] <= target) {
                left++;
            }

            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        arr[start] = arr[left];
        arr[right] = target;

        quickSort(start, left -1, arr);
        quickSort(left + 1, end, arr);
    }
}