想输出那个序列得要有一个数组记录每个数值在数列中之前的那个值,所以要多开一个
数组记录这个信息吧.
每次用binary search push进去一个之后那个数之前的一个数就是这个. 写得太烂了,
有空重写一下.
class Solution {
private:
vector s;
vector pre;
int push(int k) {
if(s.empty()){
s.push_back(k);
return -1;
}
if(k >= s.back()){
s.push_back(k);
return s[s.size()-2];
}
int l = 0, r = s.size()-1, mid;
while(l < r)
(s[mid = (l+r)/2] > k) ? r = mid : l = mid+1;
s[r] = k;
return (r-1 >= 0) ? s[r-1] : -1;
}
public:
int max_inc_seq (int a[], int n) {
int i;
for(i = 0; i < n; ++i)
pre.push_back(push(a[i]));
cout << "longest increasing: " << s.size() << '\n';
int pt = s.back();
i = n - 1;
while(pt != -1) {
cout << pt << " ";
for(; a[i] != pt ; i-- );
pt = pre[i--];
}
cout << '\n';
s.clear();
pre.clear();
return 0;
}
};