Longest Increasing Subsequence (5 ms)

solution.c

//https://leetcode.com/problems/longest-increasing-subsequence/submissions/1137805195
#include <stdint.h>

uint32_t binarySearch(int32_t* tails, uint32_t size, int32_t target) {
    uint32_t left = 0, right = size;
    while (left < right) {
        uint32_t mid = left + (right - left) / 2;
        if (tails[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

uint32_t lengthOfLIS(int32_t* nums, uint32_t numsSize) {
    int32_t tails[numsSize];
    uint32_t size = 0;
    for (uint32_t i = 0; i < numsSize; i++) {
        uint32_t pos = binarySearch(tails, size, nums[i]);
        tails[pos] = nums[i];
        if (pos == size) {
            size++;
        }
    }
    return size;
}