leetcode.最长上升子序列(longest-increasing-subsequence)

Myth丶恋晨 2022-12-27 14:29 75阅读 0赞

# 最长上升子序列(longest-increasing-subsequence) #

[题解][Link 1]  
代码一

class Solution { 
        public int lengthOfLIS(int[] nums) { 
            if (nums.length == 0) { 
                return 0;
            }
            int[] dp = new int[nums.length];
            dp[0] = 1;
            int maxans = 1;
            for (int i = 1; i < nums.length; i++) { 
                dp[i] = 1;
                for (int j = 0; j < i; j++) { 
                    if (nums[i] > nums[j]) { 
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                maxans = Math.max(maxans, dp[i]);
            }
            return maxans;
        }
    }

代码二

import java.util.Arrays;
    
    public class Solution { 
    
        public int lengthOfLIS(int[] nums) { 
            int len = nums.length;
            if (len < 2) { 
                return len;
            }
    
            int[] dp = new int[len];
            Arrays.fill(dp, 1);
    
            for (int i = 1; i < len; i++) { 
                for (int j = 0; j < i; j++) { 
                    if (nums[j] < nums[i]) { 
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            int res = 0;
            for (int i = 0; i < len; i++) { 
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode300. 最长上升子序列

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上

淡淡的烟草味﹌/ 2023年07月14日 15:58/ 0 赞/ 43 阅读

相关 leetcode300 最长上升子序列

经典题，不解释，可以看我之前文章。普通dp public class Solution { public int lengthOfLIS(in

系统管理员/ 2023年06月16日 10:35/ 0 赞/ 184 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 263 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,

川长思鸟来/ 2022年07月13日 01:55/ 0 赞/ 234 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 261 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 292 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 349 阅读

相关最长上升子序列

最长上升子序列 Time Limit: 3000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Probl

傷城~/ 2022年05月30日 10:09/ 0 赞/ 248 阅读

相关 LeetCode300最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \[

比眉伴天荒/ 2022年01月05日 04:43/ 0 赞/ 272 阅读

相关 leetcode[300] 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \

刺骨的言语ヽ痛彻心扉/ 2021年10月03日 02:34/ 0 赞/ 306 阅读