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

package org.example.test;


public class MLSTest {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 6, 7, 8, 9, 1, 2, 3, 4};
        System.out.println(MLS(arr));
    }

    /**
     * 先排序，然后计算, 重点：出现相同的，需要保存像前推。
     *
     * @param arr
     * @return
     */
    public static int MLS(int[] arr) {
        // write code here
        quickSort(arr, 0, arr.length - 1);
        int ans = 1;
        int res = 0;
        int pre = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (pre + 1 == arr[i]) {
                ans++;
            } else if (pre == arr[i]) {
                continue;
            } else {
                res = Math.max(res, ans);
                ans = 1;
            }
            pre = arr[i];
        }
        res = Math.max(res, ans);
        return res;
    }

    public static void quickSort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }

    private static int partition(int[] a, int low, int high) {
        int tmp = a[low];
        while (low < high) {
            while (low < high && a[high] >= tmp) {
                high--;
            }
            a[low] = a[high];
            while (low < high && a[low] <= tmp) {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = tmp;
        return low;
    }
}