最长递增子序列
程序员文章站
2024-02-21 18:47:04
...
1、题目描述
给定数组arr,设长度为n,输出arr的最长递增子序列。(如果有多个答案,请输出其中字典序最小的)
2、解题思路
代码可以分成两个部分:
part1:确定最长子序列,并记录位置。
part2:通过位置倒序,确定字典序最小的那组。
注意:(1)在子序列中替换不影响子序列的排序且子序列最小的数
(2)记录数字在子序列数组中的位置
3、代码
class Solution {
public:
/**
* retrun the longest increasing subsequence
* @param arr int整型vector the array
* @return int整型vector
*/
vector<int> LIS(vector<int>& arr) {
// write code here
vector<int> result;//存储结果
vector<int> pos; // 存储在结果数组中的位置
int len = arr.size();
result.push_back(arr[0]);
pos.push_back(0);
//贪心获取最长子序列
for(int i = 1;i<len;i++){
if(arr[i]>result.back()){
result.push_back(arr[i]);
pos.push_back(result.size()-1);
}else{
//在合适的位置(result是有序的,可以使用二分查找)
int j = 0;
for(j = result.size()-1;j>=0;j--){
if(result[j]<arr[i]){
break;
}
}
//替换
result[j+1] = arr[i];
pos.push_back(j+1);
}
}
//从后往前处理最长子序列
int tmpLen = result.size()-1;
for(int i = len-1;i>=0;i--){
if(pos[i]==tmpLen){
result[tmpLen] = arr[i];
tmpLen--;
}
}
return result;
}
};