大家好，又见面了，我是你们的朋友全栈君。
最长递增子序列：
给定一个长度为N的数组，找出一个最长的单调递增子序列，子序列不一定连续，但初始顺序不能乱。
例如：给定一个长度为6的数组A{4， 5， 7， 1，3， 9}，则其最长的单调递增子序列为{4，5，7，9}，长度为4。
动态规划思路：
记d[i]为以任意一个A[i]为末尾元素组成的最长递增子序列的长度，找出所有位于i之前且比A[i]小的元素A[j]，此时可
出现两种情况：
（1）若找到，例如i = 2，此时A[i] = 7，比A[i]小的元素为A[0] = 4，A[1] = 5，取所有比A[i]小的元素中A[j]中，对应的d[j]最
大的加1，即d[i] = max{ d[j] }，其中j < i 且 A[j] < A[i]；
（2）若没有找到，例如i = 3，此时A[i] = 1，i之前不存在比1小的元素，此时A[3] = 1独自构成一个递增子序列，d[i] = 1。
实现过程：
当i = 0时，此时A[0] = 4，只
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/131125.html原文链接：https://javaforall.net
