300. Longest Increasing Subsequence 最长递增子序列

题目地址：https://leetcode.com/problems/longest-increasing-subsequence/description/

题目描述

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

Example:

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

Note:

1、 TheremaybemorethanoneLIScombination,itisonlynecessaryforyoutoreturnthelength.；
2、 YouralgorithmshouldruninO(n2)complexity.；

Follow up: Could you improve it to O(n log n) time complexity?

题目大意

求数组的最长递增子序列。即LIS.

解题方法

这个题是动态规划的经典题目，其实没有那么难，只要明白其中的道理即可。在《计算机考研机试指南》P160中有详细的解答。

核心思想是使用一个数组dp来保存，dp[i]的意义是到该位置为止的最长递增子序列。

最后求所有位置的最大值，而不是dp的最后元素。

Python代码：

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        dp = [0] * len(nums)
        dp[0] = 1
        for i in range(1, len(nums)):
            tmax = 1
            for j in range(0, i):
                if nums[i] > nums[j]:
                    tmax = max(tmax, dp[j] + 1)
            dp[i] = tmax
        return max(dp)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

C++代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int N = nums.size();
        if (N == 0) return 0;
        // dp[i] means the LIS when the subsequence ends with nums[i]
        vector<int> dp(N, 1);
        for (int i = 1; i < N; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发