[leetcode]300.最長上昇サブシーケンス
6278 ワード
無秩序な整数配列を指定し、最長上昇サブシーケンスの長さを見つけます.
例:
説明:
最長上昇サブシーケンスの組み合わせが複数ある可能性がありますが、対応する長さを出力するだけでいいです.あなたのアルゴリズムの時間的複雑さはO(n 2)であるべきです.ステップアップ:アルゴリズムの時間的複雑さをO(n log n)に下げることができますか?
構想:古典的な動的計画:dp[i]にA[i]で終わる最長のサブシーケンス長を表す.A[i]には、A[i]以前の要素A[j](jdp[i]が存在する場合、すなわちA[j]で終わるLISの後にA[i]を付いたときに現在のA[i]で終わるLISよりも長く(長さが以前と等しい場合は加入せず、より長くしか加入しない、すなわちdp[j]+1>dp[i])A[j]で終わるLISの後にA[i]を付いた場合、より長いLISシーケンスが形成され、このときdp[i]=dp[j]+1である.2)A[i]以前の要素がA[i]より大きい場合、A[i]は自分でLISを形成するしかなく、長さは1である.3)境界はdp[i]=1であり、すなわち、iに対する操作のたびに、各A[i]が1つのサブシーケンスを形成すると仮定する.
状態遷移方程式:
ACコード:(C++)
例:
: [10,9,2,5,3,7,101,18]
: 4
: [2,3,7,101], 4。
説明:
最長上昇サブシーケンスの組み合わせが複数ある可能性がありますが、対応する長さを出力するだけでいいです.あなたのアルゴリズムの時間的複雑さはO(n 2)であるべきです.ステップアップ:アルゴリズムの時間的複雑さをO(n log n)に下げることができますか?
構想:古典的な動的計画:dp[i]にA[i]で終わる最長のサブシーケンス長を表す.A[i]には、A[i]以前の要素A[j](jdp[i]が存在する場合、すなわちA[j]で終わるLISの後にA[i]を付いたときに現在のA[i]で終わるLISよりも長く(長さが以前と等しい場合は加入せず、より長くしか加入しない、すなわちdp[j]+1>dp[i])A[j]で終わるLISの後にA[i]を付いた場合、より長いLISシーケンスが形成され、このときdp[i]=dp[j]+1である.2)A[i]以前の要素がA[i]より大きい場合、A[i]は自分でLISを形成するしかなく、長さは1である.3)境界はdp[i]=1であり、すなわち、iに対する操作のたびに、各A[i]が1つのサブシーケンスを形成すると仮定する.
状態遷移方程式:
dp[i]=max{1,dp[j]+1};(j=1,2…i-1&&A[j]<A[i])
ACコード:(C++)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int size = nums.size();
if (size == 0) return 0;
vector<int> dp(size, 0);
int maxLength = -1;
for (int i = 0; i < size; i++) {
dp[i] = 1;
for (int j = 0; j < size; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
};