Open Shawngbk opened 7 years ago
方法1，利用动态规划的思路，设数组length[i]表示数组前面i个数中最大增长子数组的长度。初始化设置length[i]=1{i∈[0,n)} 算法时间复杂度：O(n2) length(j) = max { length(i) + 1 : if nums[i] < nums[n] , length[j] } 0≤i≤n-1 i+1≤j≤n-1 然后取length[]数组中的最大值，返回即可 http://www.bubuko.com/infodetail-1227371.html
public class Solution { public int lengthOfLIS(int[] nums) { if(nums == null || nums.length == 0) { return 0; } int[] dp = new int[nums.length]; int res = 0; for(int i = 0; i < nums.length; i++) { dp[i] = 1; for(int j = 0; j < i; j++) { if(nums[i] > nums[j]) { dp[i] = Math.max(dp[j] + 1, dp[i]); } } if(dp[i] > res) { res = dp[i]; } } return res; } }
Microsoft
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
方法1，利用动态规划的思路，设数组length[i]表示数组前面i个数中最大增长子数组的长度。初始化设置length[i]=1{i∈[0,n)} 算法时间复杂度：O(n2) length(j) = max { length(i) + 1 : if nums[i] < nums[n] , length[j] } 0≤i≤n-1 i+1≤j≤n-1 然后取length[]数组中的最大值，返回即可 http://www.bubuko.com/infodetail-1227371.html
public class Solution { public int lengthOfLIS(int[] nums) { if(nums == null || nums.length == 0) { return 0; } int[] dp = new int[nums.length]; int res = 0; for(int i = 0; i < nums.length; i++) { dp[i] = 1; for(int j = 0; j < i; j++) { if(nums[i] > nums[j]) { dp[i] = Math.max(dp[j] + 1, dp[i]); } } if(dp[i] > res) { res = dp[i]; } } return res; } }