theme: channing-cyan highlight: arduino-light

求最长递增子序列的四种解法

动态规划 复杂度 O(n^2)

/**
 * 动态规划 复杂度 O(n^2)
 * @param nums
 * @return
 */
public static int lengthOfLIS(int[] nums) {
    int ans = 1;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    for (int j = 0; j < nums.length; j++) {
        for (int i = 0; i < j; i++) {
            if (nums[j] > nums[i]) {
                dp[j] = Math.max(dp[j], dp[i] + 1);
                ans = Math.max(ans, dp[j]);
            }
        }
    }
    return ans;
}

动态规划 + 二分优化，复杂度 O(nlogn)

/**
 * 动态规划 + 二分优化，复杂度 O(nlogn)
 * @param nums
 * @return
 */
public static int lengthOfLIS(int[] nums) {
    int cnt = 0;
    int[] sta = new int[nums.length];
    sta[cnt] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > sta[cnt]) {
            sta[++cnt] = nums[i];
            continue;
        }
        // 严格递增一定用lowBound，否则可能会出现重复，eg: [4, 10, 4]
        int pos = lowBound(sta, cnt, nums[i]);
        if (pos == -1) {
            continue;
        }
        sta[pos] = nums[i];
    }
    return cnt + 1;
}

private static int upperBound(int[] sta, int cnt, int num) {
    int l = 0, r = cnt, pos = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sta[mid] > num) {
            pos = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return pos;
}

private static int lowBound(int[] nums, int cnt, int val) {
    int l = 0, r = cnt, pos = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] >= val) {
            r = mid - 1;
            pos = mid;
        } else {
            l = mid + 1;
        }
    }
    return pos;
}

动态规划 + 树状数组优化 复杂度 O(nlogn)

/**
 * 动态规划 + 树状数组优化 复杂度 O(nlogn)
 * @param nums
 * @return
 */
public static int lengthOfLIS(int[] nums) {
    // 离散化
    int[] spread = Arrays.copyOf(nums, nums.length);
    Arrays.sort(spread);
    spread = Arrays.stream(spread).distinct().toArray();
    Map<Integer, Integer> orderMap = new HashMap<>();
    for (int i = 0; i < spread.length; i++) {
        orderMap.put(spread[i], i + 1);
    }
    int ans = 1;
    int[] c = new int[nums.length + 1];
    for (int num : nums) {
        // 查询[0, j - 1]区间最大f[i]
        int mx = query_max(orderMap.get(num) - 1, c);
        ans = Math.max(ans, mx + 1);
        // 更新 f[j] = f[i] + 1
        update_num(orderMap.get(num), mx + 1, nums.length + 1, c);
    }
    return ans;
}

private static void update_num(int num, int val, int n, int[] c) {
    for (int i = num; i < n; i += lowBit(i)) {
        c[i] = Math.max(c[i], val);
    }
}

private static int query_max(int num, int[] c) {
    int ans = 0;
    for (int i = num; i > 0; i -= lowBit(i)) {
        ans = Math.max(ans, c[i]);
    }
    return ans;
}

动态规划 + 权值线断树优化

/**
 * 动态规划 + 权值线断树优化
 * @param nums
 * @return
 */
public static int lengthOfLIS(int[] nums) {
    // 离散化
    int[] spread = Arrays.copyOf(nums, nums.length);
    Arrays.sort(spread);
    spread = Arrays.stream(spread).distinct().toArray();
    Map<Integer, Integer> orderMap = new HashMap<>();
    for (int i = 0; i < spread.length; i++) {
        orderMap.put(spread[i], i + 1);
    }
    int ans = 1;
    int[] maxVal = new int[4 * nums.length + 1];
    for (int num : nums) {
        if (orderMap.get(num) == 1) {
            tree_update_num(orderMap.get(num), 1, 1, spread.length, 1, maxVal);
            continue;
        }
        int mx = tree_query_max(1, orderMap.get(num) - 1, 1, spread.length, 1, maxVal);
        ans = Math.max(ans, mx + 1);
        tree_update_num(orderMap.get(num), mx + 1, 1, spread.length, 1, maxVal);
    }
    return ans;
}

private static void tree_update_num(int pos, int val, int l, int r, int k, int[] maxVal) {
    if (l == r) {
        maxVal[k] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        tree_update_num(pos, val, l, mid, k << 1, maxVal);
    } else {
        tree_update_num(pos, val, mid + 1, r, k << 1 | 1, maxVal);
    }
    maxVal[k] = Math.max(maxVal[k << 1], maxVal[k << 1 | 1]);
}

private static int tree_query_max(int ql, int qr, int l, int r, int k, int[] maxVal) {
    if (l >= ql && r <= qr) {
        return maxVal[k];
    }
    int mid = (l + r) >> 1, ans = 0;
    if (ql <= mid) {
        ans = Math.max(ans, tree_query_max(ql, qr, l, mid, k << 1, maxVal));
    }
    if (qr > mid) {
        ans = Math.max(ans, tree_query_max(ql, qr, mid + 1, r, k << 1 | 1, maxVal));
    }
    return ans;
}