Description

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 10^4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Answer & Explaimning

#include <stdio.h>

// Binary Search，用於在 tails 中找到第一個 >= target 的位置
int binarySearch(int* tails, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int tails[numsSize];
    int size = 0;  // tails 的有效長度

    for (int i = 0; i < numsSize; i++) {
        int pos = binarySearch(tails, size, nums[i]);
        // 如果 pos 等於 size，表示 nums[i] 可以擴展最長遞增subsequence
        if (pos == size) {
            tails[size++] = nums[i];
        } else {
            // 否則替換 tails[pos]，以保持最小結尾
            tails[pos] = nums[i];
        }
    }

    return size;
}

Testing

#include <stdio.h>

// Binary Search，用於在 tails 中找到第一個 >= target 的位置
int binarySearch(int* tails, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int tails[numsSize];
    int size = 0;  // tails 的有效長度

    for (int i = 0; i < numsSize; i++) {
        int pos = binarySearch(tails, size, nums[i]);
        // 如果 pos 等於 size，表示 nums[i] 可以擴展最長遞增subsequence
        if (pos == size) {
            tails[size++] = nums[i];
        } else {
            // 否則替換 tails[pos]，以保持最小結尾
            tails[pos] = nums[i];
        }
    }

    return size;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("Length of Longest Increasing Subsequence: %d\n", lengthOfLIS(nums, numsSize));  // 輸出應為 4
    return 0;
}