动态规划联系四—最长上升子序列

问题(力扣原题第300题)：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

思路:

动态规划 用一个数组dp[]保存给定数组中每一个元素本身对应的最大上升子序列长度，最后返回dp[]数组中的最大值.

代码:

public static int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int length = nums.length; //定义返回值初始值为1，因为会给只有一个元素的测试用例 int maxAns = 1; int[] dp = new int[length]; //dp数组中每个元素都会大于等于1 dp[0] = 1; for (int i = 1; i < length; i++) { int maxLen = 0; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { //把最大的dp[j]存到maxLen中 maxLen = Math.max(maxLen, dp[j]); } } //动态转移方程 //dp[i] = Math.max(maxLen, dp[j]) + 1;（要求nums[i] > nums[j]） dp[i] = maxLen + 1; maxAns = Math.max(dp[i], maxAns); } System.out.println(Arrays.toString(dp)); return maxAns; }

时间复杂度：

二层循环，第一层 i < length ；第二层 j < i ，去掉系数，时间复杂度为O(n²)

如果有不对的地方，请各位老铁批评指正。