东营企业网站seo,wordpress网页打开慢,网上购物系统代码,什么是网站集约化建设动态规划#xff0c;二分查找。
题目 由题#xff0c;从数组中找一个最长子序列#xff0c;不难想到#xff0c;当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看#xff0c;当遍历到这个数#xff0c;会从前面的dp选一个最大的数加上当前数#xff0c;注意…动态规划二分查找。
题目 由题从数组中找一个最长子序列不难想到当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看当遍历到这个数会从前面的dp选一个最大的数加上当前数注意这里的dp是每遍历到一个数都会加进去。而这里的dp数组同样是用来维护到某个数时的ansnums数组是做了比较的因此也有可能内循环时数组中的一些数是没有做更新的因此最后一步肯定是加上当前的数后再进行一次与更新的dp比较进行选最大。
时间复杂度O(n^2)空间复杂度O(n)。
class Solution {public int lengthOfLIS(int[] nums) {int n nums.length, ans 0;int[] f new int[n];for (int i 0; i n; i) {for (int j 0; j i; j) {if (nums[j] nums[i]) {f[i] Math.max(f[i], f[j]);}}f[i];ans Math.max(ans, f[i]);}return ans;}
}
接着是更快的用二分查找的方法在用二分时用mid去找目标值。而这里每遍历到数组的一个数时同样可以与tails的数去做比较注意如果遍历到的数与dp的数做比较时mid在大的一边没有移动过说明这个数就是大的可以追加到原数组的尾巴即有位置可以插入。
时间复杂度O(nlogn)空间复杂度O(n)。
class Solution {public int lengthOfLIS(int[] nums) {int[] tails new int[nums.length];int res 0;for(int num : nums) {int i 0, j res-1;//标准二分当左右指针重叠时再进行一次比较while(i j) {int m (i j) / 2;if(tails[m] num) i m 1;else j m - 1;}//这里的i就是目标值tails[i] num;//更新这个位置的值if(res i) res;//说明可以进行扩充//注意每次找到时res肯定会比i多一因为res从一开始的}return res;}
}很典型的一道例题可以用dp的状态维护找到前面的状态不过每到一个数都要dp两次。而二分查找目标值的方法刚好让比目标值小的存到tails数组比tails数组大的直接追加以此来更新最长递增子序列。
