题解 | 最长上升子序列(一)
最长上升子序列(一)
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 给定数组的最长严格上升子序列的长度。
* @param arr int整型一维数组 给定的数组
* @return int整型
*/
public int LIS (int[] arr) {
// write code here
int n = arr.length;
if(n == 0) return 0;
int[] dp = new int[n];
for(int i = 0; i < n; i++) {
dp[i] = 1; // 初始化最长严格上升子序列长度为 1 即该元素本身
for(int j = 0; j < i; j++) {
if(arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1); // dp[i]表示以arr[i]结尾的最长严格上升子序列的长度
}
}
}
int maxLen = 0;
for(int i = 0; i < n; i++) {
maxLen = Math.max(maxLen, dp[i]); // 找到最大的
}
return maxLen;
}
}
