在这里,我编写了一个方法maximumSortedSelection,它以元素向量作为输入(如 [1 2 3 10 7 8 9] )并返回布尔向量,其真/假表示 1/0 表示是否选择答案中的索引(如如 [1 1 1 0 1 1 1] )。
vector< bool >largestSortedSelection( vector<int>&v ){
int n = v.size();
vector< int >selectedLen(n);
vector< int >sortedList;
int maxLen = 1;
for(int i = 0; i<n; ++i){
int lb = lower_bound(sortedList.begin(),sortedList.end(),v[i])-sortedList.begin();
if( lb!=(int)sortedList.size() ){
selectedLen[i]=lb+1;
sortedList[lb]=v[i];
}
else {
sortedList.push_back(v[i]);
selectedLen[i]=(int)sortedList.size();
}
maxLen = max( maxLen, selectedLen[i] );
}
int lst = INT_MAX;//assuming maximum element will be less than INT_MAX
int len = maxLen+1;
vector< bool >selection(n,0);
for(int i = n-1; i>=0; --i ){
if( v[i]<lst && selectedLen[i]+1 == len ){
selection[i] = 1;
lst = v[i];
len--;
}
}
return selection;
}
在这种方法中:
如果您对理解源代码有困难,请告诉我。
因为我在一个循环中使用了 N 次 lower_bound 函数(其复杂度为 logN )。因此,整体时间复杂度为:O(N logN)。
内存复杂度将为O(N),因为我使用内存来保存 N 个元素。