300. 最长上升子序列(Longest Increasing Subsequence)M

英文题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

中文题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

暴力法

使用「回溯搜索」可得到输入数组的所有子序列，时间复杂度是O(2^N)，再对这些子串一次判定是否「严格上升」，时间复杂度是O(N)，所以总的时间复杂度是O(N * 2^N)

动态规划

dp[i] 表示前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取
有两种情况：
- 对于 nums[j] 和 nums[i] (j < i)，
- 1.对于 nums[j] 和 nums[i] (j<i)，使得 nums[j]≤nums[i] 且 dp[j]+1>dp[i]（即把 nums[i] 跟在以 nums[j] 结尾的LIS后面时能比当前以 nums[i] 结尾的LIS长度更长），那么就把 nums[i] 跟在以 nums[j] 结尾的LIS后面，形成一条更长的不下降子序列（遍历每一个在 i 前面的元素 j ，符合条件的令 dp[i]=dp[j]+1，会把最后最长的一个累加起来）
- 2.如果 nums[i] 之前的元素都大于 nums[i]，那么 nums[i]只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个 nums[i]
状态转移方程：dp[i]=max{1, dp[j]+1}(j=1,2,⋯,i-1 && nums[j]<nums[i])

时间复杂度O(n^2)，空间复杂度O(n)

# python3: 时间 2872 ms, 击败 39.81%; 内存 16.3 MB, 击败 49.50%
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

// c++: 时间 316 ms, 击败 16.75%; 内存 10.2 MB, 击败 44.7%
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

// java: 时间 61 ms, 击败 53.38%; 内存 41.8 MB, 击败 48.51%
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

// go: 时间 56 ms, 击败 60.42%; 内存 3.6 MB, 击败 9.8%
func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    for i := range(dp) {
        dp[i] = 1
    }
    for i := 0; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return maxSlice(dp)
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

func maxSlice(nums []int) int {
    res := nums[0]
    for _, num := range nums {
        if res < num {
            res = num
        }
    }
    return res
}

// javascript: 时间 176 ms, 击败 51.82%; 内存 42.6 MB, 击败 57.5%
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1);
    for (let i = 0; i < nums.length; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
    }
    return Math.max(...dp);
};

# 300. 最长上升子序列(Longest Increasing Subsequence)M

# 英文题目

# 中文题目

# 暴力法

# 动态规划

300. 最长上升子序列(Longest Increasing Subsequence)M

英文题目

中文题目

暴力法

动态规划