By

文章目录
  1. 1. 解析
  2. 2. 代码
  3. 3. 参考

题目

给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.

解析

此题面试中非常常见，其实比较简单，一般面试中不要慌，按条理来一般都能答出 ^_^

N长度的数组，关于最长递增子序列有max(l(i))=max(l(i-1)),i>1, a[i]>a[i-1]，这个关系式很重要
再来看假如N=1，那么l=1
如果N=2,有{16,24}，那么可以发现l=2，因为max(l(0))=1,24>16,所以max(l(1))=max(l(0))+1
好了，其实我们可以维护一个N的辅助数组，每个值表示在当前元素下考虑后面的元素可能组成的最长递增子序列,比如刚刚为N=2，有f[0]=2,f[1]=1

现在来看一个长一点的数组：

a={3,18,7,14,10,12,23,41,16,24}
我们从后往前进行遍历（第一个索引为0）
a[9]=24，为最后一个元素，所以辅助数组b中f[9]=1 表示它以及它最后可能组成的最长递增子序列为1
则有
f={_,_,_,_,_,_,_,_,_,1}
a[8]=16，所以a[8]<a[9],故f[8]=2
f={_,_,_,_,_,_,_,_,2,1}
而a[7]=41>a[8]，同时a[7]>10，所以考虑a[7]以后的元素它可能的最长递增子序列为1
f={_,_,_,_,_,_,_,1,2,1}
现在来看a[6]=23<a[41]，暂时f[6]=f[7]+1=2 再来看a[6]<a[9] 所以f[6]=f[9]+1 还是2
f={_,_,_,_,_,_,2,1,2,1}
再来看一个a[5]=12，a[5]<a[6] 故f[5]=f[6]+1=3 再继续a[7],a[8],a[9]对比之后f[5]还是等于3
f={_,_,_,_,_,3,2,1,2,1}
.
.
.
f={6,3,5,3,4,3,2,1,2,1}

然后根据数组b取降序位置的索引6，5，4，3，2，1在a上打印出来即可

这里主要是介绍动态规划法：
貌似还有最大公共子序列法以及一个插入法来求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void main(String[] args) {
	int[] a={3,18,7,14,10,12,23,41,16,24};
	int[] f=new int[a.length];//存放当前索引位置上以它为起点可能存在的最长子序列个数
	int maxIndex=-1;
	int maxLen=-1;
	
	for(int i=a.length-1;i>=0;i--)
	{
		f[i]=1;
		
		if(i==a.length-1)
			continue;
		
		for(int j=i+1;j<a.length;j++)
		{
			if(a[i]<a[j] && f[i]<=f[j])
			{
				f[i]=f[j]+1;//计算当前以当前位置为索引起始点的最长自增字符串个数
			}
		}
		
		if(f[i]>maxLen)
		{
			maxLen=f[i];//得到最长的标志
			maxIndex=i;
		}
	}
	
	for(int i=maxIndex;i<a.length;i++)
	{
		if(f[i]==maxLen)
		{
			System.out.println(a[i]);
			maxLen--;
		}
	}
}

打印结果

3
7
10
12
23
41

参考

http://qiemengdao.iteye.com/blog/1660229

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 解析
  2. 2. 代码
  3. 3. 参考