最長遞增子序列

300. Longest Increasing Subsequence (Medium)

題目描述：

??給定一個數(shù)組，找到它的最長遞增子序列

思路分析：

??動態(tài)規(guī)劃思想，定義一個數(shù)組 dp 存儲最長遞增子序列的長度，dp[n] 表示以 Sn 結(jié)尾的序列的最長遞增子序列長度。對于一個遞增子序列 {Si1, Si2,...,Sim}，如果 im < n 并且 Sim < Sn，此時 {Si1, Si2,..., Sim, Sn} 為一個遞增子序列，遞增子序列的長度增加 1。滿足上述條件的遞增子序列中，長度最長的那個遞增子序列就是要找的，在長度最長的遞增子序列上加上 Sn 就構(gòu)成了以 Sn 為結(jié)尾的最長遞增子序列。因此 dp[n] = max{ dp[i]+1 | Si < Sn && i < n} 。

代碼：

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

轉(zhuǎn)載于:https://www.cnblogs.com/yjxyy/p/11119151.html

總結(jié)

以上是生活随笔為你收集整理的动态规划（最长递增子序列）---最长递增子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。