最长上升子序列

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

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 

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

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。

  • 你算法的时间复杂度应该为 O(n2) 。
  • 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一 : O(n^2)的时间复杂度代码:

思路:(动态规划)
dp[i]表示下标取i的时候,该位置上最长的有序序列长度是多少(只是该位置最长,不一定是整体最长的序列)
在满足nums[i] > nums[j]的情况下,0 <= j < i :

  • dp[i] = max(dp[j] + 1);
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int *dp = new int[nums.size()];
        dp[0] = 1;
        int max = 1;
        for(int i = 1; i < nums.size(); ++i) {
            dp[i] = 1;
            for(int j = 0; j < i; ++j) {
                if(nums[j] < nums[i]) {
                    int temp = dp[j] + 1;
                    if(temp > dp[i])
                        dp[i] = temp;
                }
            }
            max = max > dp[i] ? max : dp[i];
        }
        return max;
    }
};

解法二 :O(nlog 2(n))

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        // dp[i]用来存放长度为i+1的序列最大的一个数值
        int *dp = new int[nums.size()];
        int max = 1; // 用于记录当前最大的长度
        dp[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            int start = 0, end = max - 1;
            // 先判断两个边界
            if(nums[i] < dp[start]) {
                dp[start] = nums[i];
                continue;
            }
            if(nums[i] > dp[end]) {
                dp[max++] = nums[i];
                continue;
            }
            // 确定是处于当前范围内
            while(start <= end) {
                int mid = (start + end) / 2;
                if(mid > 0 && dp[mid] > nums[i] && dp[mid - 1] < nums[i]) {
                    // 更新该位置的值,设置为更小的数值,方便后面添加更多大于该位置的值
                    // eg : 1 2 (4) -->  1 2 (3)
                    dp[mid] = nums[i];
                    break;
                }
                if(dp[mid] > nums[i])
                    end = mid - 1;
                else if(dp[mid] < nums[i])
                    start = mid + 1;
                else // 相等的话没必要更新
                    break;
            }
        }
        return max;
    }
};
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容