程序设计-求解最长递增子序列(C++)
2022/1/6 12:33:35
本文主要是介绍程序设计-求解最长递增子序列(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net
/* * 问题:求解最长递增子序列。 * * 分析: * 方法:动态规划。 * 设计状态:记f(i)为以a[i]结尾的LIS长度,那么LIS=max{f(i)}。 * 推导:考虑比i小的每一个j,如果a[i]>a[j],那么f(i)=f(j)+1。 * 状态转移方程:f(i)=max{f(j)}+1;其中当i>j时,a[i]>a[j]。 * * LongestIncreasingSubsequence.cpp - by LiveEveryDay */ #include <algorithm> using namespace std; int LIS(const int a[], int n) { int dp[n]; int nMax = 1; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (a[i] > a[j]) { dp[i] = max(dp[i], dp[j] + 1); } } if (dp[i] > nMax) { nMax = dp[i]; } } return nMax; } int main() { int a1[] = {1, -1, 2, -3, 4, -5, 6, -7}; printf("%d\n", LIS(a1, 8)); int a2[] = {1, 4, 3, 2, 6, 5}; printf("%d\n", LIS(a2, 6)); } // ------ Output ------ /* 4 3 */
这篇关于程序设计-求解最长递增子序列(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解