最长递增子序列

刺骨的言语ヽ痛彻心扉 2022-10-27 05:21 291阅读 0赞 
  1. /** * 输入一个无序的整数数组，请你找到其中最长递增子序列的长度 * 最长递增子序列不一定是连续的 * */
  2. public class LIS { 
  4.     public static void main(String[] args) { 
  5.         int[] nums = new int[] { 10, 9,2,5,3,7,101,18};
  6.         int res = search(nums);
  7.         System.out.println(res);
  8.     }
  10.     static int search(int[] nums) { 
  11.         int[] dp = new int[nums.length];
  12.         // dp数组值全部初始化为1，dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度
  13.         // 最长递增子序列的长度是dp数组中的最大值
  14.         Arrays.fill(dp, 1); 
  16.         //计算出dp数组中每个以nums[i]这个数结尾的最长递增子序列的长度
  17.         for (int i = 0; i < nums.length; i ++) { 
  18.             for (int j = 0; j < i; j++) { 
  19.                 if (nums[i] > nums[j]) { 
  20.                     dp[i] = Math.max(dp[i], dp[j] + 1);
  21.                 }
  22.             }
  23.         }
  24.         int res = 0;
  25.         for (int i = 0; i < dp.length; i++) { 
  26.             res = Math.max(res, dp[i]);
  27.         }
  28.         return res;
  30.     }
  32. }

发表评论

表情：
评论列表 （有 0 条评论，291人围观）

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

相关阅读

    相关 最长递增子序列

    问题 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A\{5， 6， 7， 1， 2， 8\}，则其...

    曾经终败给现在曾经终败给现在/ 0 赞/ 192 阅读

    相关 最长递增子序列

    给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的） 例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

    灰太狼灰太狼/ 0 赞/ 378 阅读

    相关 最长递增子序列

    最长递增子序列问题的求解   最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么显而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由

    桃扇骨桃扇骨/ 0 赞/ 334 阅读