最长单调递增子序列 python_最长单调递增子序列

前面三篇博客分别讲了贪心，递归，分治，今天就说个简单的动态规划(DP)的题目吧。在我心中DP算是比较难的算法，尤其像状态DP，树形DP，因为实力问题就说一个简单的线性DP——最长单调递增子序列。

题目如下：

计算一个给定整数序列的最长单调递增子序列的长度(最优值)及该序列内容(最优解)。给定一个序列X＝{x1,x2,…xn}，{xi1,xi2,…,xim}称为X的一个长度为m的单调递增子序列，如果满足i1

思路我就不作太多的分析了就一个最简单普通的DP问题，代码里有注释，考虑到osc上好多童鞋对java代码感兴趣所以这次贴的是java代码。下面的代码的时间是O(n*n)不是最优，但是好理解，优化的可以将顺序查找改为二分查找

代码如下：

/*

* 最长单调递增子序列

* 1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度;

* 2)序列的a的最长单调子序列的长度为max{b[i],0=

* 3)b[i] = max{b[k],a[k]<=a[i]&&0=

*

* auther:thj

*/

public class LIS

{

private int[] a;

private int[] b;

public LIS(int[] a)

{

this.a = a;

b = new int[a.length];

}

public void lis()

{

b[0] = 1;

for (int i = 0; i < a.length; i++)

{

int k = 0;

for (int j = 0; j < i; j++)

{

if (a[j] <= a[i] && k < b[j])

{

k = b[j];

}

}

b[i] = k + 1;

}

int k = max(b);

//输出结果

print(k);

}

//求数组中最大值下标

private int max(int[] b)

{

int max = b[0];

int k = 0;

for (int i = 0; i < b.length; i++)

{

if (max < b[i])

{

max = b[i];

k = i;

}

}

return k;

}

//输出

public void print(int k)

{

for (int i = k - 1; i >= 0; i--)

{

if (b[k] == b[i] + 1 && a[i] <= a[k])

{

print(i);

break;

}

}

System.out.print(a[k] + " ");

}

public static void main(String[] args)

{

int[] a = {5, 2, 4, 6, 5, 1, 8};

LIS lis = new LIS(a);

lis.lis();

}

}