300. Longest Increasing Subsequence

Question

LeetCode Problem

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
• -10^4 <= nums[i] <= 10^4
  Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solutions

Use dynamic programming to solve this: (this approach is pretty regular, there would have follow up⚠️)

• dp 定義：dp[i] 為nums[i] 內最長的遞增數組長度。其中 j 為 0 ~ i 內的位置。 rule: j < i
• 遞推公式： dp[i] = max(dp[i], dp[j] + 1)

time complexity: O(N^2)
space complexity: O(N)

int lengthOfLIS(vector<int> &nums) {
	size_t m = nums.size();
	if (m == 0) return 0;
	vector<int> dp(m, 1);
	int maxLen = 1;
	for (int i = 1; i < m; ++i) {
		for (int j = 0; j < i; ++j) {
			if (nums[i] > nums[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
			maxLen = max(dp[i], result);
		}
	}
	return maxLen;
}

Use binary search (a better time complexity 👍🏻)

int lengthOfLIS(vector<int> & nums) {
	
}