LIS 最长上升子序列的长度 LeetCode 300

package com.dp;
/**
** @author wanglj
** @time 2020-7-29 23:36:17
** @filecomment 
** @fileName Solution.java
** @packageName com.dp
** @Todo  LIS LC300 最长上升子序列的长度
**/
//i状态可以从在它之前比它小的数字状态转换过来
/** 例如nums{2,3,5,1,6}* dp[0] = 1 {2}* dp[1] = max{dp[0]+1,0+1} = 2，{2，3}* dp[2] = max{dp[0]+1,dp[1]+1，1}  = 3; {2，3，5}* dp[3] = 1 {1}* dp[4] = max{dp[0]+1,dp[1]+1,dp[2]+1,dp[3]+1,1} = 4;{2,3,5,6}* res = max{dp[i]}* */
import java.util.Arrays;
public class Solution {public int lengthOfLIS(int[] nums) {if(nums.length==0){return 0;}int n = nums.length;int[] dp = new int[n+1];dp[0] = 1;Arrays.fill(dp, 1);for(int i = 1;i < n;i++) {for(int j = 0;j < i;j++) {if(nums[j]<nums[i]) {dp[i] = Math.max(dp[j]+1, dp[i]);}else {continue;}}}int res = dp[0];for(int i = 1;i < n;i++) {if(dp[i]>res) {res = dp[i];}}return res;}
}//测试代码
package com.dp;import java.util.Arrays;//动态规划  最长上升子序列的长度
//LC 300 Longest Increasing Subsequence
/*Given an unsorted array of integers, find the length of longest increasing subsequence.Example:Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. */
public class LIS {public void lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = 1;Arrays.fill(dp, 1);for(int i = 1;i < n;i++) {for(int j = 0;j < i;j++) {if(nums[j]<nums[i]) {dp[i] = Math.max(dp[j]+1, dp[i]);}else {continue;}}}int res = dp[0];for(int i = 1;i < n;i++) {if(dp[i]>res) {res = dp[i];}System.out.println(dp[i]);}
//		return res;}public static void main(String[] args) {LIS soLis = new LIS();int[] nums = new int[] {10,9,2,5,3,7,101,18} ;
//		System.out.println(soLis.lengthOfLIS(nums));soLis.lengthOfLIS(nums);}
}