334递增的三元子序列贪心算法（思路解析+源码）
文章目录
- 题目
- 思路解析
- 源码
- 总结
题目
思路解析
有两种解法：解法一：动态规划（利用dp找到数组最长递增序列长度，判断是否大于3即可）本题不适用，因为时间复杂度为O（n^2），超时。
解法二：贪心算法：解法如上图，题目要求长度为三，设置第一个元素为长度1的值，是指长度二的值为无穷大。根据下图，以【2,1，5,0，4,6】这个数组为例，先设置长度1为2，长度2为正无穷，从数组第二个数开始比较，1比长度2的正无穷小，在看长度1，1比长1的2小，进行覆盖为1。数组第三个数5比长度1的1大，比长度2的正无穷小进行覆盖。0比长度1的1小进行覆盖。4比长度2的5小进行覆盖。最后一个数为6，为长度3的值。