An intuitive DP along with an optimised tricky solution in C, well-commented

• ``````//AC - 28ms - a DP solution;
int lengthOfLIS(int* nums, int size)
{
if(size < 2) return size;
int *lens = (int*)malloc(sizeof(int)*size); //store the LIS length for each index;
lens[0] = 1;
int max = 1;
for(int i = 1; i < size; i++) //start from index 1 to avoid special case in inner loop;
{
int t = 0; //used to store the LIS length before index i which must be smaller than nums[i];
for(int j = i-1; j >= 0; j--) //check all its previous index to update the current;
if(nums[i] > nums[j] && lens[j] > t)
t = lens[j];
lens[i] = t+1;
if(lens[i] > max) //update the max;
max = lens[i];
}
return max;
}
``````

``````int binarySearch(int* nums, int size, int target)
{
int l=0, r=size-1;
while(l < r)
{
int m = l+(r-l)/2;
if(nums[m] > target) r = m-1;
else if(nums[m] < target) l = m+1;
else break;
}
if(nums[l] < target) return l+1; //ensure the index is pointed to the position whose element is equal to or bigger than the target;
else return l;
}

//AC - 0ms - using stack to collect the LIS;
int lengthOfLIS(int* nums, int size)
{
int top = -1;
int *arr = (int*)malloc(sizeof(int)*size);
for(int i = 0; i < size; i++)
{
int pos = binarySearch(arr, top+1, nums[i]);
if(pos > top) arr[++top] = nums[i]; //a new element should be appended;;
else arr[pos] = nums[i]; //make the element pos pointing to smaller;
}