LeetCode 300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

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] <= 104

 

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

Sol 1: O(N * N)

	class Solution {
	public:
	/*
	Framework
	1. function
	dp[i]: i th index ended LIS max
	2. relation
	dp[i] = max(1, dp[j] + 1 (if nums[j] <= nums[i]) )
	3. base
	dp[0] = 1;
	time: O(n * n)
	space: O(n)
	*/
	int lengthOfLIS(vector<int>& nums) {
	int n = nums.size();
	vector<int> dp(n, 0);
	int ans = 0;
	// bottom-up
	for(int i = 0; i < n; i++){
	// base
	dp[i] = 1;
	// relation
	for(int j = 0; j < i; j++){
	if(nums[i] > nums[j])
	dp[i] = max(dp[i], dp[j] + 1);
	}
	ans = max(ans, dp[i]);
	}
	return ans;
	}
	};

view raw 300. Longest Increasing Subsequence.cpp hosted with ❤ by GitHub

Sol 2: O(N * log N)

	class Solution {
	public:
	/*
	Binary Search
	time: O(n * logn)
	space: O(n)
	*/
	int lengthOfLIS(vector<int>& nums) {
	vector<int> sub;
	for(auto n: nums){
	if(!sub.size())
	sub.push_back(n);
	else {
	// append
	if(sub[sub.size() - 1] < n){
	sub.push_back(n);
	}
	// binary search & update
	else {
	auto it = lower_bound(sub.begin(), sub.end(), n);
	*it = n;
	}
	}
	}
	return sub.size();
	}
	};

view raw 300. Longest Increasing Subsequence.cpp (n * logn) hosted with ❤ by GitHub