1.题目
2.思路
当前i指向的数，与i’之前的元素（用j表示）进行比较，如果当前的数大，开始更新dp[i]的值。
dp[i]代表到达i元素的最长递增子序列的长度。
3.代码实现
public class H31 {public int lengthOfLIS(int[] nums) {//如果数组为空，直接返回 0。if(nums.length==0){return 0;}// 定义一个 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。// 创建 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度int[] dp=new int[nums.length];// 第一个元素的最长子序列长度为 1（只有自己）dp[0]=1;// 用于记录所有 dp[i] 中的最大值，即最终答案int max=1;for(int i=1;i<nums.length;i++) {// 从第二个元素开始遍历，i走的比较快dp[i]=1;// 初始时，dp[i] 至少是 1（即自己本身）for(int j=0;j<i;j++) {//j从第0个元素开始if (nums[i] > nums[j]) {//如果 nums[i] 可以接在 nums[j] 后面形成递增序列dp[i] = Math.max(dp[i], dp[j] + 1); // 更新 dp[i] 为所有可能连接的 dp[j] + 1 中的最大值}}max=Math.max(max,dp[i]);// 更新全局最大值 maxans}return max;// 返回整个数组中的最长递增子序列长度}public static void main(String[] args){H31 test=new H31();int[] nums={10,9,2,5,3,7,101,18};int length=test.lengthOfLIS(nums);System.out.println(length);}
}
