广州建站推广,ic外贸平台排行,做素材网站存储问题,做免费网站LeetCode:300.最长递增子序列
300. 最长递增子序列 - 力扣#xff08;LeetCode#xff09;
1.思路
dp[i]的状态表示以nums[i]为结尾的最长递增子序列的个数。 dp[i]有很多个#xff0c;选择其中最大的dp[i]Math.max(dp[j]1,dp[i])
2.代码实现 1class Solution {2 pub…LeetCode:300.最长递增子序列
300. 最长递增子序列 - 力扣LeetCode
1.思路
dp[i]的状态表示以nums[i]为结尾的最长递增子序列的个数。 dp[i]有很多个选择其中最大的dp[i]Math.max(dp[j]1,dp[i])
2.代码实现 1class Solution {2 public int lengthOfLIS(int[] nums) {3 int[] dp new int[nums.length];4 Arrays.fill(dp, 1);5 for (int i 1; i nums.length; i) {6 for (int j 0; j i; j) {7 if (nums[j] nums[i]) {8 dp[i] Math.max(dp[j] 1, dp[i]);9 }
10 }
11 }
12 int res 0;
13 for (int i 0; i nums.length; i) {
14 res Math.max(res, dp[i]);
15 }
16 return res;
17 }
18}3.复杂度分析
时间复杂度O(n). 空间复杂度O(n).
LeetCode: 674. 最长连续递增序列
674. 最长连续递增序列 - 力扣LeetCode
1.思路
后一个状态是由当前状态推出来的注意边界值…
2.代码实现 1class Solution {2 public int findLengthOfLCIS(int[] nums) {3 int[] dp new int[nums.length];4 Arrays.fill(dp, 1);56 for (int i 0; i nums.length - 1; i) { 78 if (nums[i 1] nums[i]) {9 dp[i 1] dp[i] 1;
10 }
11 }
12 int res 0;
13 for (int i 0; i dp.length; i) {
14 res Math.max(dp[i], res);
15 }
16 return res;
17 }
18}3.复杂度分析
时间复杂度O(n). 空间复杂度O(n).
LeetCode:718. 最长重复子数组
718. 最长重复子数组 - 力扣LeetCode
1.思路
动规dp[i][j]定义很关键当前状态需要前一个状态推导出来。
2.代码实现 1// 暴力解法2class Solution {3 public int findLength(int[] nums1, int[] nums2) {4 int maxLength 0;5 for (int i 0; i nums1.length; i) {6 for (int j 0; j nums2.length; j) {78 int length 0;9 int p1 i;
10 int p2 j;
11
12 while (p1 nums1.length p2 nums2.length nums1[p1] nums2[p2]) {
13 length;
14 p1;
15 p2;
16 }
17 maxLength Math.max(maxLength, length);
18 }
19 }
20 return maxLength;
21 }
22}
23
24// 动规
25class Solution {
26 public int findLength(int[] nums1, int[] nums2) {
27 int res 0;
28 int[][] dp new int[nums1.length 1][nums2.length 1];
29
30 for (int i 1; i nums1.length 1; i) {
31 for (int j 1; j nums2.length 1; j) {
32 if (nums1[i - 1] nums2[j - 1]) {
33 dp[i][j] dp[i - 1][j - 1] 1;
34 res Math.max(res, dp[i][j]);
35 }
36 }
37 }
38 return res;
39 }
40}3.复杂度分析
时间复杂度O(n^2). 空间复杂度O(n).
