# Sharing my O(nlogn) solution

• O(N^2) solution:

``````//longest increasing subsequence O(nlogn) implementation
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
//use a val_min, val_min[k] indicates the smallest value with a increasing subsequence k
vector<int> val_min(1, nums[0]);
int len = 1;

for (int i = 1; i < n; i++) {
int curVal = nums[i];
int k = len;
for (; k > 0; k--) {
if (curVal > val_min[k-1]) break;
}
if (k == len) {
val_min.push_back(curVal); len++;
} else {
val_min[k] = curVal;
}
}
return len;
}
};
``````

Optimize it to O(n*logn) using binary search:

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
//use a val_min, val_min[k] indicates the smallest value with a increasing subsequence k
vector<int> val_min(1, nums[0]);
int len = 1;

for (int i = 1; i < n; i++) {
int curVal = nums[i];
int k = binarySearch(1, len, val_min, curVal);
if (k == len) {
val_min.push_back(curVal); len++;
} else {
val_min[k] = curVal;
}
}
return len;
}

int binarySearch(int begin, int end, vector<int> val_min, int target) {
if (target > val_min[end-1]) return end;
if (target <= val_min[begin-1]) return begin - 1;
int first = begin - 1, last = end - 1;
while (first <= last) {
int mid = (first + last) / 2;
if (val_min[mid] >= target) {
last = mid - 1;
} else {
if (val_min[mid] < target && val_min[mid+1] >= target)
return mid + 1;
first = mid + 1;
}
}
return -1;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.