**问题：**最长递增子序列问题主要分为了两类，即最长连续递增子序列的求解，以及最长递增子序列的求解（不一定要连续）。求解过程总结如下： 算法标签：动态规划、深度优先搜索、二分查找 代码：01_dp求解最长连续递增子序列长度
#include
#include
using namespace std;
const int maxN = 1e5+9;
int dp[maxN]; // dp[i]表示以第i个元素作为最后元素的最长连续递增子序列的的长度
int res = -1;
int main(){
int n;
int arr[maxN];
cin >> n;
for( int i=1; i<=n; i++ ){
cin >> arr[i];
}
dp[1] = 1;
for( int i=2; i<=n; i++ ){
if(arr[i] > arr[i-1]){
dp[i] = dp[i-1] + 1;
}else{
dp[i] = 1;
}
res = max(res, dp[i]);
}
cout << res;
return 0;
}
代码：02_dp求最长递增子序列长度(n*n)
#include
#include
using namespace std;
const int maxN = 1e5+9;
int dp[maxN]; // dp[i]表示以第i个元素作为最后元素的最长递增子序列的长度
int res = 1;
int main(){
int n;
int arr[maxN];
cin >> n;
for( int i=1; i<=n; i++ ){
cin >> arr[i];
}
for( int i=1; i<=n; i++ ){
dp[i] = 1;
for( int j=1; j<=i-1; j++ ){
if(arr[i] > arr[j]){
dp[i] = max(dp[i], dp[j]+1);
}
}
res = max(res, dp[i]);
}
cout << res;
return 0;
}
代码：03_dp求最长递增子序列长度(n*logn)
#include
using namespace std;
const int maxN = 1e5 + 9;
int n, res;
int dp[maxN]; // 存储当前伪最长上升子序列[与真实最长上升子序列的长度相同]
int main(){
int arr[maxN];
cin >> n;
for( int i=1; i<=n; i++ ){
cin >> arr[i];
}
dp[1] = arr[1];
res = 1;
for( int i=2; i<=n; i++ ){
if(arr[i] > dp[res]){
dp[++res] = arr[i];
}else{
int tmp = lower_bound(dp+1, dp+res+1, arr[i]) - dp;
dp[tmp] = arr[i];
}
}
cout << res;
return 0;
}
代码：04_dfs求解最长递增子序列
#include
#include
#include
using namespace std;
int dp[100009];
int res = 0;
string ans;
void dfs(int currentIndex, int previousIndex, string tmp, string str){
if(currentIndex == str.length()){
if(res < tmp.length()){
ans = tmp;
res = tmp.length();
}
return;
}
if(currentIndex == 0 || str[currentIndex] > str[previousIndex]){
dfs(currentIndex+1, currentIndex, tmp+str[currentIndex], str);
dfs(currentIndex+1, previousIndex, tmp, str);
}else{
dfs(currentIndex+1, previousIndex, tmp, str);
dfs(currentIndex+1, previousIndex, ""+str[currentIndex], str);
}
}
int main(){
string str;
cin >> str;
dfs(0, -1, "", str);
cout << ans;
return 0;
}
推荐阅读
发表评论