Question

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

求算法思想以及C源代码。运行成功就给分！

Answer 1

算法导论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]<<" ";
}

Answer 2

贪心算法就行.

建立一个栈,然后顺序扫描整个序列.
第一个元素先放入栈中,
以后扫描到的每一个元素,如果其比栈顶元素大,则压入栈中;如果比栈顶元素小,则逐个弹栈,直到发现栈顶元素比它小.
时刻记录栈的长度,并记录其最大值.当序列扫描完成后,栈的最大长度就是最长序列,而处于最大长度时的栈中的元素,就是最大递增序列.
这个算法是O(N^2)级别的,但是比dp要快一点.

追问

思想什么的都知道了 就是那个代码啊 求代码！大神！！！
课程设计的作业

追答

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