/**

* @program JavaBooks

* @description: 最长上升子序列

* @author: mf

* @create: 2020/04/17 22:14

*/

package subject.dp;

/**

* 输入: [10,9,2,5,3,7,101,18]

* 输出: 4

* 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

*/

public class T6 {

public int lengthOfLIS(int[] nums) {

if (nums.length == 0) return 0;

int[] dp = new int[nums.length];

dp[0] = 1;

int lis = 1;

for (int i = 1; i < dp.length; i++) {

dp[i] = 1;

for (int j = 0; j < i; j++) {

if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {

dp[i] = dp[j] + 1;

}

}

lis = Math.max(lis, dp[i]);

}

return lis;

}

}