Longest Increasing Subsequence
March 22, 2014
DP
很久不写算法了== 写个东西练练手
最长上升子序列
输入n，然后是数组a[ ]的n个元素
输出最长上升子序列的长度
一、最简单的方法复杂度O(n * n)
DP[ i ] 是以a[ i ] 为结尾的最长上升子序列的长度。
DP[ i ] = max{DP[ j ] + 1 | j < i && a[ j ] < a[ i ]}
代码：
/*
* =====================================================================================
* Filename : LongestIncrSub1.cpp
* Description : O(n^2)
* Version : a better Algorithm of O(n^2)
* Created : 03/22/14 22:03
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : How about today?
* =====================================================================================
*/
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstdlib>
const int MAXN = 1001;
int dp[MAXN], a[MAXN];
int n, i, j;
int
main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("LongestIncrSub.txt", "r", stdin);
#endif /* ----- not ONLINE_JUDGE ----- */
while ( ~scanf("%d", &n) ) {
for ( i = 0; i < n; ++i ) {
scanf ( "%d", &a[i] );
dp[i] = INT_MAX;
}
for ( i = 0; i < n; ++i ) {
for ( j = 0; j < n; ++j ) {
if ( j == 0 || dp[j-1] < a[i] ) {
if ( dp[j] > a[i] ) {
dp[j] = a[i];
}
}
}
}
int result = 1;
for ( j = n - 1; j >= 0; --j ) {
if ( dp[j] != INT_MAX ) {
result = j + 1;
break;
}
}
printf ( "%d\n", result );
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
二、因为长度相同的几个不同的子序列中，最末位数字最小的在之后比较有优势，所以用DP针对这个最小的末尾元素求解。
DP[ i ] 表示长度为 i + 1的上升子序列中末尾元素的最小值
从前往后扫描数组a[ ]，对于每一个元素a[ i ]，只需要在DP[ ] 数组中找到应该插入的位置。
if j == 0 || a[ i ] > DP[ j-1 ]
DP[ j ] = min{ DP[ j ], a[ i ]}
由于对于每个a[ i ] 都要扫描一遍DP[ ] 数组，所以复杂度还是O(n * n)
代码：
/*
* =====================================================================================
* Filename : LongestIncrSub1.cpp
* Description : O(n^2)
* Version : a better Algorithm of O(n^2)
* Created : 03/22/14 22:03
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : How about today?
* =====================================================================================
*/
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstdlib>
const int MAXN = 1001;
int dp[MAXN], a[MAXN];
int n, i, j;
int
main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("LongestIncrSub.txt", "r", stdin);
#endif /* ----- not ONLINE_JUDGE ----- */
while ( ~scanf("%d", &n) ) {
for ( i = 0; i < n; ++i ) {
scanf ( "%d", &a[i] );
dp[i] = INT_MAX;
}
for ( i = 0; i < n; ++i ) {
for ( j = 0; j < n; ++j ) {
if ( j == 0 || dp[j-1] < a[i] ) {
if ( dp[j] > a[i] ) {
dp[j] = a[i];
}
}
}
}
int result = 1;
for ( j = n - 1; j >= 0; --j ) {
if ( dp[j] != INT_MAX ) {
result = j + 1;
break;
}
}
printf ( "%d\n", result );
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
三、对于上一个算法，在DP[ ]数组中找a[ i ]元素的插入位置的时候，采用的是线性查找，由于DP[ ]这个数组是有序的，所以可以采用二分，这要复杂度就降到了O(nlogn)，可以用STL函数lower_bound用来找第一个大于等于a[ i ]的位置。
代码：
/*
* =====================================================================================
* Filename : LongestIncrSub2.cpp
* Description : A better solution
* Version : algorithm of O(nlogn)
* Created : 03/22/14 22:37
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : How about today?
* =====================================================================================
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;
const int MAXN = 1001;
int a[MAXN], dp[MAXN];
int i, n, result;
int
main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("LongestIncrSub.txt", "r", stdin);
#endif /* ----- not ONLINE_JUDGE ----- */
while ( ~scanf("%d", &n) ) {
fill(dp, dp + n, INT_MAX);
for ( i = 0; i < n; ++i ) {
scanf ( "%d", &a[i] );
}
for ( i = 0; i < n; ++i ) {
*lower_bound(dp, dp + n, a[i]) = a[i];
}
result = lower_bound(dp, dp + n, INT_MAX) - dp;
printf ( "%d\n", result );
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
Source Code on GitHub
四、如何打印出最长上升子序列呢？
用一个position数组，position[ i ] 表示位置 i 的数字在上升子序列中的位置。也就是，插入dp数组中的位置。
比如
然后在position数组中从后往前找到第一次出现的3对应的a[ i ] = 8，然后接着找第一次出现的2对应的a[ i ] = 3，然后接着找第一次出现的1对应的a[ i ] = 2，最后接着
找第一次出现的0对应的a[ i ] = -7
所以，-7, 2, 3, 8就是最长上升子序列的一个解。这个解是在序列中最后出现的。
代码：
/*
* =====================================================================================
* Filename : LongestIncrSub2.cpp
* Description : A better solution
* Version : algorithm of O(nlogn)
* Created : 03/22/14 22:37
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : How about today?
* =====================================================================================
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;
const int MAXN = 1001;
int a[MAXN], dp[MAXN], position[MAXN], sub[MAXN];
int i, n, result;
int
main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
// freopen("LongestIncrSub.txt", "r", stdin);
#endif /* ----- not ONLINE_JUDGE ----- */
while ( ~scanf("%d", &n) ) {
fill(dp, dp + n, INT_MAX);
for ( i = 0; i < n; ++i ) {
scanf ( "%d", &a[i] );
}
int *tmp;
for ( i = 0; i < n; ++i ) {
tmp = lower_bound(dp, dp + n, a[i]);
position[i] = tmp - dp;
*tmp = a[i];
}
result = lower_bound(dp, dp + n, INT_MAX) - dp;
printf ( "%d\n", result );
int t = result - 1;
for ( i = n - 1; i >= 0; --i ) {
if ( t == position[i] ) {
sub[t] = a[i];
--t;
}
}
for ( i = 0; i < result; ++i ) {
if ( i ) {
printf ( " " );
}
printf ( "%d", sub[i] );
}
printf ( "\n" );
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
所有的代码在github里面