一、问题
有一个长为n的数列 a0,a1,a2...,an-1a。请求出这个序列中最长的上升子序列的长度和对应的子序列。上升子序列指的是对任意的i < j都满足ai < aj的子序列。
二、思路
如果i < j且ai < aj则认为ai到aj存在有向边，由于一个数不可能直接或间接的指向自己，所以是一个有向无环图。但是，在这里我们并不需要真正的建立图。我们可以用动态规划来做，对于状态的设定有多种方式。
三、代码实现
1、将dp[i]表示以ai结束的最长上升子序列,当j < i且a[j] < a[i],dp[i] = max(dp[i],dp[j] + 1)，初始化dp[i] = 1。由于定义的是结束位置，所以记录的是逆序，用栈倒过来再输出就行。
代码一：
#include<stdio.h>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = + ;
int n;
int a[maxn], dp[maxn]; //dp[i]表示以i结束的最长上升子序列
int nextp[maxn]; //记录路径
int res = ;
int first = ; void print_ans()
{
stack<int>s;
for (int i = ; i < res; i++)
{
s.push(first + );
first = nextp[first];
}
for (int i = ; i < res; i++)
{
int tmp = s.top(); s.pop();
printf("%d ", tmp);
}
printf("\n%d\n", res);
} void slove()
{
memset(dp, , sizeof(dp));
memset(nextp, , sizeof(nextp));
res = ; first = ; //记得清零
for (int i = ; i < n; i++)
{
dp[i] = ;
for (int j = ; j < i; j++)
{
if (a[j] < a[i])
{
if (dp[j] + > dp[i])
{
dp[i] = dp[j] + ;
nextp[i] = j;
}
}
}
if (dp[i] > res)
{
res = dp[i];
first = i;
}
}
print_ans();
} int main()
{
while (scanf("%d", &n) == && n)
{
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
slove();
}
return ;
}
代码二：两者只是输出的处理不同，用逆向寻路，不需要额外的空间，但要消耗一些时间。
#include<stdio.h>
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = + ;
int n;
int a[maxn], dp[maxn]; //dp[i]表示以i结束的最长上升子序列
stack<int>sta; void print_ans(int s)
{
sta.push(s + );
if (dp[s] == )
{
while (!sta.empty())
{
int tmp = sta.top(); sta.pop();
printf("%d ", tmp);
}
return;
}
for (int i = ; i < n; i++)
{
if (a[i] < a[s] && dp[s] == dp[i] + )
{
print_ans(i);
break;
}
}
}
void slove()
{
memset(dp, , sizeof(dp));
int res = ;
int first = ;
stack<int>s;
for (int i = ; i < n; i++)
{
dp[i] = ;
for (int j = ; j < i; j++)
{
if (a[j] < a[i])
{
dp[i] = max(dp[i],dp[j] + );
}
}
if (dp[i] > res)
{
res = dp[i];
first = i; //first记录最长上升子序列的最后元素的位置
}
} print_ans(first);
printf("\n%d\n", res);
} int main()
{
while (scanf("%d", &n) == && n)
{
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
slove();
}
return ;
}
2、用dp[i]表示以i开始的最长上升子序列，初始化同样是dp[i] = 0。同时由于定义的是开始位置，可以直接输出最长上升子序列。
void print_ans()
{
for (int i = ; i < res; i++)
{
printf("%d ", first + );
first = nextp[first];
}
printf("\n%d\n", res);
} void slove()
{
res = ; //定义成全局变量时，注意清零
for (int i = n - ;i >= ; i--)
{
dp[i] = ;
for (int j = i + ; j < n; j++)
{
if (a[i] < a[j])
{
if (dp[j] + > dp[i])
{
dp[i] = dp[j] + ;
nextp[i] = j;
}
}
}
if (dp[i] > res)
{
res = dp[i];
first = i;
}
}
print_ans();
}
3、把dp[i]表示长度为i + 1的上升子序列中末尾元素的最小值（不存在的话就是INF）。
贪心 + 二分查找，利用贪心思想，对于一个一个上升子序列，显然最后一个元素越小，越有利于添加新的元素，这样序列就越长。
类似的我们也可以定义对称的状态，即把dp[i]表示长度为i + 1的上升子序列中开始元素的最大值
相比前面的状态定义，有两个好处：如果子序列长度相同，可以使最末尾元素的值最小；时间复杂度由O(n^2)降至O(nlogn)。
开始全部初始化为INF，如果i == 0或者dp[i - 1] < aj,dp[i] = min(dp[i],aj),最终dp[i] < INF,最大的i + 1就是结果。如何找到aj呢，由于dp[i]记录的长度为i + 1的最末尾元素的最小值，而最末尾元素是这个长度为i+1中的最大值，所以aj大于dp[i]就能更新。我们还能发现，dp单增，每个aj只需用来更来一次。
n个元素，每次查找logn,总的时间复杂度为O(nlogn).
void slove()
{
fill(dp, dp + n, INF);
for (int i = ; i < n; i++)
{
*upper_bound(dp, dp + n, a[i]) = a[i];
}
int first = lower_bound(dp, dp + n, INF) - dp;
printf("%d\n", dp[first - ]);
printf("%d\n", first);
}
打印结果路径似乎不太方便，以后再补上吧。