最长递增子序列(Longest increasing subsequence)

时间:2021-03-22 06:50:55

问题定义:

给定一个长度为N的数组A,找出一个最长的单调递增子序列(不要求连续)。

这道题共3种解法。

1. 动态规划

动态规划的核心是状态的定义和状态转移方程。定义lis(i),表示前i个数中以A[i]结尾的最长递增子序列的长度。可以得到以下的状态转移方程:

d(i) = max(, d(j) + ), 其中j < i,且A[j] <= A[i]

程序实现:

int longestIncreasingSubsequence(vector<int> nums)
{
if (nums.empty())
return ;
int len = nums.size();
vector<int> lis(len, ); for (int i = ; i < len; ++i)
{
for (int j = ; j < i; ++j)
{
if (nums[j] < nums[i] && lis[i] < lis[j] + )
lis[i] = lis[j] + ;
}
}
return *max_element(lis.begin(), lis.end());
}

程序复杂度为O(N^2)

2. 动态规划 + 二分查找

换一种角度看问题。令Ai,j表示所有长度为j的最大递增子序列的最小末尾,我们有Ai,1 < Ai,2 < ... < Ai,j。

对A[i+1]来说,有两种选择。

1. Ai,j < A[i+1], 此时我们可以得到一个长度为i+1的最大递增子序列。

2. 替换Ai,k,如果Ai,k-1 < A[i+1] < Ai,k。

替换长度为k的最大递增子序列的最小末尾,是为了增大获取更长子序列的机会。

程序实现:

int binarySearch(const int arr[], int low, int high, int val)
{
while (low <= high)
{
int mid = low + (high - low) / ; // Do not use (low + high) / 2 which might encounter overflow issue if (val < arr[mid])
high = mid - ;
else if (val > arr[mid])
low = mid + ;
else
return mid;
}
return low;
}
int LIS(int arr[], int n)
{
int *minTail = new int[n];
minTail[] = arr[];
int len = ;
for (int i = ; i < n; ++i)
{
if (arr[i] > minTail[len-])
minTail[len++] = arr[i];
else
{
int pos = binarySearch(minTail, , len-, arr[i]);
minTail[pos] = arr[i];
}
}
delete [] minTail;
return len;
}

复杂度:O(nlogn)

reference :

最长递增子序列(LIS)

3. 排序+LCS

这种方法就不细说了。。。