一、什么是最长不下降子序列
最长不下降子序列（Longest Increasing Subsequence，简称LIS）是指在一个序列中，找出一个最长的子序列满足单调递增。其中的单调递增是指数列中后一个数大于前一个数的情况。比如序列[3,1,4,1,5,9,2,6,5,3,5,8,9,7]的最长不下降子序列是[1,2,3,5,8,9]。
二、最长不下降子序列的求解方法
我们介绍两种方法：动态规划和二分查找法。
1. 动态规划法
动态规划的实现是通过维护一个计数数组dp，用来记录以每个元素为结尾的子序列中最长的LIS长度。我们先初始化dp数组为1，因为每个单独的元素的LIS都是1。
int lengthOfLIS_dp(int* nums, int numsSize) {
if(numsSize <= 1) return numsSize;
int dp[numsSize];
for(int i=0; i<numsSize; i++) dp[i] = 1;
int maxLen = 1;
for(int i=1; i<numsSize; i++) {
for(int j=0; j<i; j++) {
if(nums[j] maxLen) ? dp[i] : maxLen;
}
return maxLen;
}
该算法的时间复杂度是O(n^2)，空间复杂度是O(n)。
2. 二分查找法
该方法需要维护一个数组tails，其中tails[i]保存长度为i+1的LIS的最小末尾元素。由于tails长度是不断增加的，因此我们需要一个变量size来维护tails的当前有效长度。
每次遍历数组nums，对于每个元素num，我们在tails中寻找第一个大于等于num的位置index，将tails[index]更新为num，如果index等于size，则表明新增了一条长度为size+1的LIS，需要将size加1。
int lengthOfLIS_binarySearch(int* nums, int numsSize) {
int tails[numsSize];
int size = 0;
for(int i=0; i<numsSize; i++) {
int left = 0, right = size;
while(left < right) {
int mid = (left+right)/2;
if(tails[mid] < nums[i]) left = mid+1;
else right = mid;
}
tails[left] = nums[i];
if(left == size) size++;
}
return size;
}
该算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。
三、最长不下降子序列的实际应用
最长不下降子序列在实际应用中有很多使用场景。这里以纸牌游戏为例，介绍一下如何将LIS算法应用到游戏中。
现在有一组扑克牌，每张牌都有一个权重weight，我们将这些牌分为两部分，分别排列成两个序列a和b。每次可以从a或b的顶部取走一张牌，并将该牌放置在一个额外的序列c的顶部。请问当序列a和b遍历完毕后，序列c的最长不下降子序列的长度是多少？
这个问题可以很自然地转化为求解在序列a和b中取出若干个数后，它们的最长不下降子序列的长度。我们将a和b的元素对应相加，得到一个新的序列，然后求新序列的最长不下降子序列长度即可解决问题。
int max(int a, int b) {
return (a>b) ? a : b;
}
int lengthOfLIS_game(int* a, int aSize, int* b, int bSize) {
int c[aSize];
for(int i=0; i<aSize; i++) c[i] = a[i]+b[i];
int dp[aSize];
for(int i=0; i<aSize; i++) dp[i] = 1;
int maxLen = 1;
for(int i=1; i<aSize; i++) {
for(int j=0; j<i; j++) {
if(c[j] < c[i]) {
dp[i] = max(dp[i], dp[j]+1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
四、结语
本文介绍了最长不下降子序列的定义、求解方法和实际应用。动态规划和二分查找法都是常用的LIS求解方法，它们的时间和空间复杂度有所不同，选择不同的算法取决于具体应用场景。在游戏开发中，LIS算法可以被广泛地应用，为游戏增添了一份趣味和挑战。
原创文章，作者：FISV，如若转载，请注明出处：https://www.506064.com/n/142997.html
微信扫一扫 
支付宝扫一扫 