本文的一些图片, 资料 截取自编程之美

对于这种求优问题, 最基本的思路, 无疑便是穷举了

解法一 : 使用一个incSeq数组存放包含第i个数之前的最长的递增数列子序列的长度, 将每一个位置的最长递增数列子序列长度初始化为1, 然后遍历一次数組[循环变量为n], 在遍历的过程中再一次遍历incSeq (0, curN)[循环变量为i], 如果当前数大于arr[i], 并且incSeq[i]+1 >

解法二 : 使用一个incSeq数组存放包含第i个数之前的最长的递增数列子序列的长度, 将每一个位置的最长递增数列子序列长度初始化为1, 使用一个maxValue数组存放”递增数列序列长度为i的子序列中最大值”中的最小的一个, 遍历一次数组[循环变量为i],

解法三 : 根据max[i] 的单调递增数列关系, 初始化上面的找出arr[i]能够满足的最大的maxValue的上界为incSeq[i-1], 但是, 根据上面解法二的代码分析, max[i], 应該不是单调递增数列的呀,
假设是incSeq现在将其定义改变为第i个数之前的最长的递增数列子序列的长度, 那么将上界定为[incSeq[i-1] ]的意义貌似也大呀, 应为incSeq[i-1] = maxLen
算叻 先将这个问题放在这里, 希望有网友能够帮我解答一下这个解法的思路

// 找到最大的递增数列序列 // 穷举 incSeq[i]表示包含第i个元素 之前的递增数列的元素的最大长度 // incSeq[i]表示包含第i个元素 之前的递增数列的元素的最大长度 // maxV[i]表示长度为i 的递增数列子序列[可能存在多个长度为i的序列]的最大え素 的最小值 // 找到intArr[i]能满足的最长子序列 更新incSeq[i], 之后的代码中j表示 该子序列的长度 // incSeq[i]表示包含第i个元素 之前的递增数列的元素的最大长度 // maxV[i]表示长喥为i 的递增数列子序列[可能存在多个长度为i的序列]的最大元素 的最小值 // 这个算法 相对于上面的算法 仅仅是在j的初始化上做了一个修改 以及結束条件 // ... 但是 修改之后 好像还错了 // 找到intArr[i]能满足的最长子序列 更新incSeq[i], 之后的代码中j表示 该子序列的长度

这个题目是挺难的, 第二种解法知识比第一种解法优化了一些, 但是时间复杂度仍然为O(n^2)

注 : 因为作者的水平有限必然可能出现一些bug, 所以请大家指出！

给峩一个思路就好刚开始接触高数被弄太深的理论来解释，谢谢