动态规划C++实现–最长递增子序列

动态规划C++实现–最长递增子序列题目:给定数组arr,返回arr的最长递增子序列。举例:arr=[2,1,5,3,6,4,8,9,7],返回的最长递增子序列为[1,3,4,8,9]要求:如果arr长度为N,请实现时间复杂度为O(NlogN)的方法。一、先介绍时间复杂度O(N^2)的方法,具体过程如下:1.生成长度为N的数组dp,dp[i]表示在以arr[i]这个数结尾的情况下,arr[0…

大家好,又见面了,我是你们的朋友全栈君。

题目: 给定数组arr, 返回arr的最长递增子序列

举例:arr = [2, 1, 5, 3, 6, 4, 8, 9, 7], 返回的最长递增子序列为 [1, 3, 4, 8, 9]

要求:如果arr长度为N,请实现时间复杂度为O(NlogN)的方法。

目录: 一、 时间复杂度O(N^2)的方法

           二、 时间复杂度O(NlogN)的方法

一、 先介绍时间复杂度O(N^2)的方法,具体过程如下:

1. 生成长度为N的数组dp, dp[i]表示在以arr[i]这个数结尾的情况下,arr[0…i]中的最大递增序列长度。

2. 对第一个数arr[0]来说,令dp[0] = 1,接下来,从左到右依次计算出每个数结尾的情况下的最长递增序列长度。

3. 计算dp[i],如果最长递增子序列以arr[i]结尾,那么arr[0,…,i-1]中所有比arr[i]小的数都可以作为倒数第二个数

    所以 dp[i] = max{ dp[j] + 1} (0 <=j < i, arr[j] < arr[i]), 如果arr[0,…,i-1]中所有数都不比arr[i]小,令dp[i] = 1。

4.根据求出的dp数组,得到最长递增子序列。遍历dp数组,找到最大值以及位置,并开始逆序还原出决策路径。

代码如下:

// 最长递增序列 <动态规划> <复杂度0(N^2)>
#include<bits/stdc++.h>
using namespace std;
vector<int> getdp1(vector<int> &arr);
vector<int> generateLIS(vector<int> &arr, vector<int>&dp);


int main() {
    vector<int> arr;
    int temp;
    while(cin >> temp){
        arr.push_back(temp);
    }
    vector<int> dp = getdp1(arr);
    vector<int> lis = generateLIS(arr, dp);
    for (int i = 0; i < lis.size(); i++){
        cout << lis[i]<<" ";
    }
    return 0;
}


vector<int> getdp1(vector<int> &arr){
    vector<int> dp(arr.size(), 0);
    for(int i = 0; i < arr.size(); i++){
        dp[i] = 1;
        for (int j = 0; j < i; j++){
            if (arr[j] < arr[i]){
                dp[i] = max(dp[j]+ 1, dp[i]);
            }
        }
    }
    return dp;
}


vector<int> generateLIS(vector<int> &arr, vector<int> &dp){
    int len = 0; int index = 0;
    for (int i = 0; i < dp.size(); i++) { //寻最长递增子序列末尾的位置和值
        if (dp[i] > len) {
            len = dp[i];              // 最长序列长度
            index = i;                // 最长序列末位置
        }
    }
    vector<int> lis(len, 0);
    lis[--len] = arr[index];
    for (int i = index; i >= 0; i--){
        if (arr[i] < arr[index] && dp[i] == dp[index] - 1){  //从后往前找子序列
            lis[--len] = arr[i];
            index = i;
        }
    }
    return lis;
}
/* input
2 1 5 3 6 4 8 9 7
*/
/* output
1 3 4 8 9
*/

编译器:codeblocks

输入:

动态规划C++实现--最长递增子序列

输出:

动态规划C++实现--最长递增子序列

二、 再介绍时间复杂度O(NlogN)的方法,具体过程如下:

计算dp数组的过程达到时间复杂度O(NlogN),这里采用二分查找进行优化,先生成一个长度为N的数组ends和变量right.

遍历的过程中ends[0,…,right]有效区,ends[right+1,…,N-1]无效区,

ends[b] = c 表示遍历到目前为止,在所有长度为b+1的递增序列中,最小的结尾数为c.

以arr=[2,1,5,3,6,4,8,9,7]为例进行说明:

1. 初始时,dp[0]=1, ends[0]=2, rights = 0, 有效区 ends[0…0],ends[0] = 2, 长度为1,结尾为2

2. arr[1] = 1, 在有效区ends[0,…0]找最左边大于或等于arr[1]的数,发现ends[0] =2 >arr[1], 表示以arr[1]结尾的最长序列只有

    一 个,dp[1] = 1, ends[0] = 1 (用1替换了原来的2)

3. arr[2] = 5, 在有效区ends[0,..0]找最左边大于或等于arr[2]的数,发现并没有,则ends的有效长度+1, end[1] = 5, 有效区

   扩大,dp[2] = 2. arr[0,1] = {1, 5}

依此类推:

代码如下:

// 最长递增序列 <动态规划> <复杂度0(NlogN)>
#include<bits/stdc++.h>
using namespace std;
vector<int> getdp2(vector<int> &arr);
vector<int> generateLIS(vector<int> &arr, vector<int>&dp);


int main() {
    vector<int> arr;
    int temp;
    while(cin >> temp){
        arr.push_back(temp);
    }
    vector<int> dp = getdp2(arr);
    vector<int> lis = generateLIS(arr, dp);
    for (int i = 0; i < lis.size(); i++){
        cout << lis[i]<<" ";
    }
    return 0;
}


vector<int> getdp2(vector<int> &arr){
    vector<int> dp(arr.size(), 0);
    vector<int> ends(arr.size(), 0);
    ends[0] = arr[0]; dp[0] = 1;
    int right = 0; int l = 0; int r = 0; int m = 0;
    for (int i = 1; i < arr.size(); i++) {
        l = 0;
        r = right;
        while(l <= r) {      //二分法
            m = (l + r) / 2;
            if (arr[i] > ends[m]){
                l = m + 1;
            }else {
                r = m - 1;
            }
        }
        right = max(right, l);
        ends[l] = arr[i];
        dp[i] = l + 1;
    }
    return dp;
}


vector<int> generateLIS(vector<int> &arr, vector<int> &dp){
    int len = 0; int index = 0;
    for (int i = 0; i < dp.size(); i++) { //寻最长递增子序列末尾的位置和值
        if (dp[i] > len) {
            len = dp[i];
            index = i;
        }
    }
    vector<int> lis(len, 0);
    lis[--len] = arr[index];
    for (int i = index; i >= 0; i--){
        if (arr[i] < arr[index] && dp[i] == dp[index] - 1){  //从后往前找子序列
            lis[--len] = arr[i];
            index = i;
        }
    }
    return lis;
}
/* input
2 1 5 3 6 4 8 9 7
*/
/* output
1 3 4 8 9
*/

编译器:codeblocks

输入:

动态规划C++实现--最长递增子序列

输出:

动态规划C++实现--最长递增子序列

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/134209.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • MATLAB柱状图画法(详细)

    首先先给一张柱状图,请注意,ABC三个对比的数据,是分别对应一个数组的每一列,然后贴代码figure(1)axes2=axes(‘position’,[0.1,0.1,0.86,0.8]);%这个是figure里面图的位置和大小,分别为离下边,左边的距离,还有图的高和宽bar(mse_lowhigh);set(gca,’XTickLabel’,{‘0.5′,’1’,’…

  • waitforsingleobject的作用_效率理论

    waitforsingleobject的作用_效率理论MicrosoftWindows平台中两种最常用的锁定方法为WaitForSingleObject和EnterCriticalSection。WaitForSingleObject是一个过载MicrosoftAPI,可用于检查和修改许多不同对象(如事件、作业、互斥体、进程、信号、线程或计时器)的状态。WaitForSingleObject的一个不足之处是它会始终获取内核的锁

  • 淘宝准点秒杀脚本

    淘宝准点秒杀脚本腾讯云服务器优惠购买链接:1核2G云服务器首年88元:http://url.cn/5Z0ZWGI准备软件下载地址:https://download.csdn.net/download/tangcv/11968538pycharm文件太大,不好上传,直接去官网下载:https://www.jetbrains.com/pycharm/download/#section=windo…

  • CSS 鼠标样式「建议收藏」

    CSS 鼠标样式「建议收藏」巧合要用到鼠标样式效果,就顺便整理了下十五种CSS鼠标样式,小例子供大家使用啊。CSS鼠标样式语法如下:任意标签中插入style=”cursor:*” 例子:文本或其它页面元素 文本或其它页面元素 注意把*换成如下15个效果的一种:下面是对这15种效果的解释。移动鼠标到解释上面,看看你的鼠标起了什么变化吧!hand是手型   例子:CSS鼠标手型效果 CSS

  • 我是如何自学C语言的(一个菜鸟的学习路)「建议收藏」

    我是如何自学C语言的(一个菜鸟的学习路)「建议收藏」—————————————————————————————————————————零基础扫盲课:计算机科学速成课(扫盲课):http://www.bilibili.com/video/av21376839?…

  • 集成学习-Voting

    集成学习-Voting一、什么是集成学习集成学习是使用一系列学习器进行学习,并使用某种规则把各个学习结果进行整合从而获得比单个学习器更好的学习效果的一种机器学习方法。一般情况下,集成学习中的多个学习器都是同质的”弱学习器”。上面的描述来自百度百科,看定义的话知道是基于‘弱学习器’的,很多讲集成学习的教程都会先讲决策树,然后讲到随机森林和GBDT,也就是bagging和boosting,…

    2022年10月31日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号