问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

设计一个O(n2)时间算法,找出由n个数组成的序列的最长单调递增子序列

发布网友 发布时间:2022-05-09 17:44

我来回答

2个回答

热心网友 时间:2023-10-11 02:34

算法导论15.4-5 请给出一个O(n^2)时间的算法,使之能找出一个n个数的序列中最长的单调递增子序列。

这个题目是在动态规划部分,此处显然是要用到动态规划。

我们知道可以使用动态规划思想的问题的的两个重要的特征是具有最优子结构和重叠子问题。下面就来分析一下这个问题:

对于一个n个元素的序列nums,设其最长单调递增子序列为Sm(n)(m为递增子序列的长度),则对于Sm存在两种情况:

1、如果nums[n]比Sm-1的最后一个元素大,则Sm由Sm-1加nums[n]组成

2、如果nums[n]小于等于Sm-1的最后一个元素,则Sm即为Sm-1

但是这样考虑有问题,因为如果Sm-1的序列有多个,我们则应该每一个都与nums[n]考察,如果nums[n]比所有Sm-1的尾元素都小或相等,而Sm-2的序列中又存在尾元素小于nums[n]的序列,则我们应该如何选择,Sm应该是多少?
Sm-1+nums[n]、Sm-1、Sm-2+nums[n]

所以之前的分析是有问题的,在长度相同的情况下,我们优先选择包含nums[n]的序列作为Sm(n),因为每一个新加入的元素都可能改变不同长度的递增子序列,因此我们需要维护每一个递增子序列以获取最优。

这里的最优子结构就是n个元素的最长递增子序列是从前n-1个元素结尾的递增子序列中的一个或者再加上nums[n],这里面自然存在很多重叠子问题。

代码如下:

/************************************************************************/
/* 算法导论15.4-5
* 找出n个数的序列中最长的单调递增子序列
* 利用动态规划思想,时间复杂度为O(n^2)*/
/************************************************************************/
#include<iostream>
using namespace std;
void printSequence(int *b,int* nums,int last);
int main()
{
int n=8;
int nums[9]={0,1,7,8,9,2,3,4,5};
//b存储当前元素所在递增子序列中当前元素的前一个元素序号
//c存储以当前元素结尾的递增子序列长度
//last存储当前元素为止的序列中最长递增子序列的最后一个元素的序号
//maxLen存储当前最长递增子序列的长度
int b[9]={0},c[9]={0},last[9]={0},maxLen=0;
c[1]=1,last[1]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<i;j++)
{
if(nums[j]<nums[i] && c[j]+1>c[i])
{
c[i]=c[j]+1;
b[i]=j;
last[i]=i;
maxLen=c[i];
}else if(c[j]>c[i]){
maxLen=c[j];
last[i]=last[j];
}
}
}
cout<<"原序列长度为"<<n<<",如下:"<<endl;
for (int i=1;i<=n;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl<<"最长递增子序列长度为"<<maxLen<<",如下:"<<endl;
printSequence(b,nums,last[n]);
cout<<endl;
return 0;
}

void printSequence(int *b,int* nums,int last)
{
if(b[last]>0)
printSequence(b,nums,b[last]);
cout<<nums[last]<<" ";
}

热心网友 时间:2023-10-11 02:35

贪心算法就行.

建立一个栈,然后顺序扫描整个序列.
第一个元素先放入栈中,
以后扫描到的每一个元素,如果其比栈顶元素大,则压入栈中;如果比栈顶元素小,则逐个弹栈,直到发现栈顶元素比它小.
时刻记录栈的长度,并记录其最大值.当序列扫描完成后,栈的最大长度就是最长序列,而处于最大长度时的栈中的元素,就是最大递增序列.
这个算法是O(N^2)级别的,但是比dp要快一点.追问思想什么的都知道了 就是那个代码啊 求代码!大神!!!
课程设计的作业

追答手头没有c的编译器.你不至于不会编码吧? 至少写个大概,不懂的具体问.

声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
为什么word换行的时候不对齐? 老人各类心脏病的急救方法有哪些呢? 老人心脏病突然发作怎么办 老人突发心脏病该如何急救呢? TAO黄子韬 tao什么学校毕业? 红楼梦第14回特色句92句精选 今天出院又入院医保 FPM看这一篇就够了 “更何入他不二门”的出处是哪里 怎么解决一下问题 有5个人有7个数字分别是1234567,每个人每天只可以选其中一个数字,如何让5个人的数加起来每天凑成20,共7天 动态时间规整的动态时间规整的原理描述 生物信息学动态规划法为什么减少了运算空间与时间 中国和韩国哪个强大 韩国、中国、日本这三个亚洲国家哪个对外经济依赖最强? 计算逆矩阵 中国和韩国哪个科技水平更高 韩国是不是比朝鲜的靠山—中国还要强大? 韩国人和中国人谁有钱? 什么是动态时间规划算法 DTW 还是弹性匹配算法吗? 韩国军事实力强吗?比如武器有我们中国的强? 动态规划算法的时间和空间复杂度是多少 中国和韩国军事实力,谁厉害! 韩国人厉害还是我们中国人厉害 韩国发达还是中国发达? 大韩民国厉害还是中国厉害啊? 中国经济厉害还是韩国厉害 中国实力与韩国比起来那个更强? 中国和韩国哪个国家厉害些,?? 梦见三条龙在天空中飞,飞了一会过后要往岩石里面钻,那些石头就往下掉,是什么意思 动态规划分配礼物问题 DTW算法,我在网上下载了matlab的DTW(动态时间规整)算法的程序,里面计算两个不同维度向量的匹配距离。 请问背包问题的时间复杂度不是一个多项式时间复杂度如何解释? 梦见三条龙连续从头顶飞过什么意思? 多段图动态规划算法的计算时间是O(n+e),这里的e是什么意思呢?怎么得到的? 女人梦见金色三条龙在天上飞: 姜锡肇 被抓 中海油姜锡肇被抓 梦见别人来例假血止不住 动力定位系统的DP3动力系统 中海油李宁因何被抓 当女孩子说讨厌你我怎么回? 女生说讨厌你,男生说为什么女生该怎么回答 女人说越来越讨厌你了什么意思? 女生讨厌你怎么办? 凉皮调出来是红色的放了什么 蒸出的凉皮隔夜变红色是什么原因 凉皮有红色绿色黑色的吗? 历代皇帝在位与年龄