最长上升子序列

Posted on Aug 09, 2024 By ᵇᵒ

LIS

LeetCode 300

Given an integer array nums, return the length of the longest strictly increasing subsequence.

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

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        // dp[i] 表示前 i + 1 个数的最大上升子序列个数
        val dp = IntArray(nums.size) { 1 }
        for (i in nums.indices) {
            var max = 1
            for (j in 0 until i) {
                if (nums[j] < nums[i]) max = max.coerceAtLeast(dp[j] + 1)
            }
            dp[i] = max
        }
        return dp.max()
    }
}

贪心 + 二分查找 复杂度 \(O(n\log{n})\)

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val sub = IntArray(nums.size)
        var length = 0
        for (n in nums) {
            var index = sub.binarySearch(n, 0, length)
            if (index < 0) index = -(index + 1)
            sub[index] = n
            if (index == length) length++
        }
        return length
    }
}

动态规划 + 树状数组 复杂度 \(O(n\log{n})\)

方案一：

class BIT(size: Int) {
    private val bit = IntArray(size + 1)

    fun get(index: Int): Int {
        var max = 0
        var i = index
        while (i > 0) {
            max = max.coerceAtLeast(bit[i])
            i -= i.and(-i)
        }
        return max
    }

    fun update(index: Int, value: Int) {
        var i = index
        while (i < bit.size) {
            bit[i] = bit[i].coerceAtLeast(value)
            i += i.and(-i)
        }
    }
}

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val bit = BIT(nums.size)
        nums.mapIndexed { i, n ->
            Pair(i + 1, n)
        }.sortedWith { (i1, n1), (i2, n2) ->
            if (n1 == n2) i2 - i1 else n1 - n2
        }.forEach { (index, num) ->
            var max = bit.get(index - 1)
            bit.update(index, ++max)
        }
        return bit.get(nums.size)
    }
}

方案二：

class BIT(size: Int) {
    private val bit = IntArray(size + 1)

    fun get(index: Int): Int {
        var max = 0
        var i = index
        while (i > 0) {
            max = max.coerceAtLeast(bit[i])
            i -= i.and(-i)
        }
        return max
    }

    fun update(index: Int, value: Int) {
        var i = index
        while (i < bit.size) {
            bit[i] = bit[i].coerceAtLeast(value)
            i += i.and(-i)
        }
    }
}

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val min = nums.min()
        val max = nums.max()
        val bit = BIT(max - min + 1)
        for (n in nums) {
            bit.update(n - min + 1, bit.get(n - min) + 1)
        }
        return bit.get(max - min + 1)
    }
}

求 LIS 个数

LeetCode 673

// todo

求 LIS 具体序列

ZOJ 4028

// todo