1 class UVa1471{
 2 public:
 3     int FindLongestCombinedSubSeq(vector<int> &v){
 4         size_t len = v.size();
 5         // Index is the length of existing sub sequence, value is the rightmost value of the subsequence
 6         vector<int> minR(len, RMAX);
 7         int prev = INT_MIN, seq = 0, maxSeqLen = 0;
 8         for(size_t i = 0; i < len; i++){
 9             if(v[i] > prev){
10                 seq++;
11             }else{
12                 int lo = i - seq;
13                 for(int k = 0; k < seq; k++){
14                     int num = v[lo + k];
15                     // Consider right part of current sequence, num as left element, find previous sub sequcence which right end element < num.
16                     int prevSeqLen = binSearch(minR, num);
17                     maxSeqLen = max(maxSeqLen, prevSeqLen + seq - k);
18                     // Consider left part of current sequence, num as right element, replace existing sub sequence if its righ end element > num.
19                     int leftPartLen = k + 1;
20                     minR[leftPartLen] = min(minR[leftPartLen], num);
21                 }
22                 seq = 1;
23             }
24             prev = v[i];
25         }        
26         int lo = len - seq;
27         for(int k = 0; k < seq; k++){
28             int prevSeqLen = binSearch(minR, v[lo + k]);
29             maxSeqLen = max(maxSeqLen, prevSeqLen + seq - k);
30         }        
31         return maxSeqLen;
32     }
33     
34 private:
35     const int RMAX = 0x3f3f3f3f;
36     int binSearch(vector<int> &v, int k){
37         size_t lo = 0, hi = v.size() - 1;
38         // invariant: the largest element < k is in [lo, hi]
39         while(lo < hi){
40             size_t m = lo + (hi - lo + 1)/2;
41             if(v[m] >= k){
42                 hi = m - 1;
43             }else{
44                 lo = m;
45             }
46         }
47         return lo;
48     }
49 };