http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 using namespace std; 10 11 int maxsum(int arr[], int n) { 12 vector<int> tail; 13 tail.push_back(arr[0]); 14 for (int i = 1; i < n; i++) { 15 if (arr[i] < tail[0]) tail[0] = arr[0]; 16 else if (arr[i] > tail[tail.size()-1]) tail.push_back(arr[i]); 17 else { 18 int mid; 19 int left = 0; 20 int right = tail.size() - 1; 21 while (left < right) { 22 mid = (left + right) / 2; 23 if (tail[mid] < arr[i]) left = mid + 1; 24 else right = mid - 1; 25 } 26 mid = (left + right) / 2; 27 tail[mid] = arr[i]; 28 cout << "tail[" << mid << "] is arr[" << i << "] = " << arr[i] << endl; 29 } 30 } 31 return tail.size(); 32 } 33 34 int main() { 35 int arr[9] = {2, 5, 3, 7, 11, 8, 10, 13, 6}; 36 cout << maxsum(arr, 9) << endl; 37 return 0; 38 }