LeetCode最長増分子配列のO(nlogn)詳細
7262 ワード
/***************************************************************************** * * Given an unsorted array of integers, find the length of longest increasing * subsequence. * * For example, * Given [10, 9, 2, 5, 3, 7, 101, 18], * The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. * Note that there may be more than one LIS combination, it is only necessary for yo * to return the length. * * Your algorithm should run in O(n2) complexity. * * Follow up: Could you improve it to O(n log n) time complexity? * * Credits: * Special thanks to @pbrother for adding this problem and creating all test cases. * *****************************************************************************/ 最も長い増分サブシーケンスを求めます.この問題ではこのシーケンスは要求されていません.そのため、前の数より大きい数を配列に押し込むだけで、1つの数がその配列の中で最大の数より小さい場合は、配列の中で2点を探してその位置を見つけます.
以下、この最長増分子シーケンスを求めるシーケンスであり、dp[i]はi位置で終わる最長増分子シーケンスの個数である.
//
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (int i = 0; iif (v.size() == 0 || v.back()else {
int low = 0, high = v.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (v[mid]1;
else high = mid - 1;
}
v[low] = nums[i];
}
}
return v.size();
}
以下、この最長増分子シーケンスを求めるシーケンスであり、dp[i]はi位置で終わる最長増分子シーケンスの個数である.
#include
#include
#include
#include
using namespace std;
// DP
vector<int> getLIS(vector<int> &num){
vector<int> ivec; //help
int length = num.size();
vector<int> dp(length);
dp[0] = 1;
ivec.push_back(num[0]);
for (int i = 1; i < length; ++i) {
if (ivec.back() < num[i]) {
ivec.push_back(num[i]);
dp[i] = dp[i - 1] + 1;
}
else {
int low = 0, high = ivec.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (ivec[mid] < num[i])
low = mid + 1;
else
high = mid - 1;
}
ivec[low] = num[i];
dp[i] = low + 1;
}
}
return dp;
}
//
vector<int> subArray(vector<int> &nums,vector<int> &dp) {
int len = 0, index = 0;
for (int i = 0; i < dp.size(); i++) {
if (dp[i] > len) { //
len = dp[i];
index = i;
}
}
vector<int> result(len);
result[--len] = nums[index];
for (int i = index; i >= 0; i--) {
if (nums[i] < nums[index] && dp[i] == dp[index] - 1) {
result[--len] = nums[i];
index = i;
}
}
return result;
}
int main() {
vector<int> n = { 3,5,6,2,5,4,19,5,6,7,12 };
vector<int>dp = getLIS(n);
vector<int>result = subArray(n, dp);
for (auto c : result)
cout << c << endl;
}