最长递增子序列问题【C++】-创新互联

**问题：**最长递增子序列问题主要分为了两类，即最长连续递增子序列的求解，以及最长递增子序列的求解（不一定要连续）。求解过程总结如下：
算法标签：动态规划、深度优先搜索、二分查找
代码：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)

#includeusing 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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：最长递增子序列问题【C++】-创新互联
链接地址：http://cxhlcq.com/article/csgpie.html