力扣第300题-最长递增子序列1.本题可以使用动态规划来解dp数组含义为到当前元素为止的最大递增子序列长度所有元素自身就是一个子序列都初始化为1。遍历一遍数组找到比当前元素小的值看当前元素是否要接续到该元素后面则递推公式为dp[i] fmax(dp[i], dp[j] 1)。完整代码如下1. int lengthOfLIS(int* nums, int numsSize) { 2. // dp[i]以nums[i]结尾的最长递增子序列长度 3. int dp[numsSize]; 4. dp[0] 1; 5. // 记录全局最长递增子序列长度 6. int res 1; 7. 8. // 遍历每个数字作为子序列末尾 9. for (int i 1; i numsSize; i){ 10. // 初始自身构成长度为1的子序列 11. dp[i] 1; 12. // 遍历i之前所有数字寻找更小的前缀 13. for (int j 0; j i; j){ 14. // 前面数字更小可拼接形成更长子序列 15. if (nums[j] nums[i]) dp[i] fmax(dp[i], dp[j] 1); 16. } 17. // 更新全局最大值 18. res fmax(res, dp[i]); 19. } 20. 21. return res; 22. }该算法时间复杂度为O(n2)空间复杂度为O(n)。2.本题的进阶方法需要使用贪心二分方法贪心的策略就是“要想长得长每次就得长得慢”。维护一个数组d存储“长度为i的递增子序列的最小末位元素”。遍历数组如果当前元素比d的最后一个元素大说明可以直接接续上去递增子序列的长度也1否则就去数组d中进行二分查找找出第一个比该元素大的元素进行替换。形象地说d数组记录着各个长度下的“最佳潜力股”。3.基于以上思想可写出完整代码如下1. int lengthOfLIS(int* nums, int numsSize) { 2. if (numsSize 0) { 3. return 0; 4. } 5. 6. // d 数组长度最多为 numsSize 1 7. // d[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值 8. // 注意d 数组的索引是从 1 开始的d[1] 到 d[len] 9. int* d (int*)malloc(sizeof(int) * (numsSize 1)); 10. 11. d[1] nums[0]; // 初始化长度为 1 的最佳结尾是第一个元素 12. int len 1; // 当前最长递增子序列的长度 13. 14. for (int i 1; i numsSize; i) { 15. // 如果当前数字比目前最长序列的结尾还要大直接追加长度 1 16. if (nums[i] d[len]) { 17. len; 18. d[len] nums[i]; 19. } 20. else { 21. // 否则使用二分查找在 d[1] 到 d[len] 中找 22. // 找什么找最后一个小于 nums[i] 的数字的位置 23. int l 1, r len, pos 0; 24. 25. while (l r) { 26. int mid l (r - l) / 2; // 防止溢出的标准写法 27. 28. if (d[mid] nums[i]) { 29. // 找到了一个比 nums[i] 小的数先记录下它的位置然后继续往右边逼近 30. pos mid; 31. l mid 1; 32. } else { 33. // 如果 d[mid] nums[i]说明我们要找的在左半边 34. r mid - 1; 35. } 36. } 37. 38. // 循环结束后pos 是最后一个【严格小于】nums[i] 的元素的位置 39. // 那么 pos 1 就是第一个【大于等于】nums[i] 的元素的位置 40. // 用 nums[i] 替换掉它使得该长度的序列末尾变得更小潜力更大 41. // (特例如果所有数都 nums[i]pos 还是初始值 0此时刚好更新 d[1] nums[i]) 42. d[pos 1] nums[i]; 43. } 44. } 45. 46. // 释放动态分配的内存 47. free(d); 48. 49. // d 数组的最终长度就是整个数组的最长递增子序列的长度 50. return len; 51. }该算法时间复杂度为O(nlogn)空间复杂度为O(n)。力扣第674题-最长连续递增序列1.本题先尝试使用动态规划来做dp数组的含义为“当前长度下的最长连续递增序列的长度”dp[0]初始化为1。遍历一遍数组当前元素比上一个元素大时将计数器cnt 1取dp[i – 1]和cnt 1中的较大值否则就将cnt置为1并让dp[i]的值保持和dp[i – 1]一致。完整代码如下1. int findLengthOfLCIS(int* nums, int numsSize) { 2. // dp[i]前i个元素中最长连续递增子数组长度 3. int dp[numsSize]; 4. dp[0] 1; 5. // cnt以当前i结尾的连续递增子数组长度 6. int cnt 1; 7. 8. for (int i 1; i numsSize; i){ 9. if (nums[i] nums[i - 1]){ 10. // 当前数字比前一个大连续长度1 11. cnt; 12. dp[i] fmax(dp[i - 1], cnt); 13. } else { 14. // 不满足递增连续长度重置为1 15. cnt 1; 16. dp[i] dp[i - 1]; 17. } 18. } 19. 20. return dp[numsSize - 1]; 21. }该算法时间复杂度和空间复杂度均为O(n)。2.本题还是使用贪心算法更简便只要目前满足递增就将计数器cnt 1否则就将res和cnt的较大值存入rescnt置为1。最后不要忘记额外进行一次res fmax(res, cnt)来防止数组本身就是一个连续递增序列的情况。完整代码如下1. int findLengthOfLCIS(int* nums, int numsSize) { 2. // res全局最长连续递增子数组长度 3. int res 1; 4. // cnt以当前位置结尾的连续递增子数组长度 5. int cnt 1; 6. for (int i 1; i numsSize; i){ 7. if (nums[i] nums[i - 1]){ 8. // 保持连续递增当前连续长度1 9. cnt; 10. } else { 11. // 递增中断更新全局最大值并重置当前连续长度 12. res fmax(res, cnt); 13. cnt 1; 14. } 15. } 16. // 处理数组末尾一段连续递增未更新res的情况 17. res fmax(res, cnt); 18. 19. return res; 20. }该算法时间复杂度为O(n)空间复杂度为O(1)。
