About Software: [LeetCode] 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

<Solution>

和 674. Longest Continuous Increasing Subsequence 同思路，但比較簡單點

code 如下

Java
Time complexity O(n^2)

	class Solution {
	public int lengthOfLIS(int[] nums) {
	if(nums.length < 2) {
	return nums.length;
	}

	int[] lengths = new int[nums.length];
	lengths[0] = 1;

	int ans = 1, localMax = 0;

	for(int i = 1; i < nums.length; i++) {
	localMax = 0;
	for(int j = 0; j < i; j++) {
	if(nums[j] < nums[i]) {
	localMax = Math.max(localMax, lengths[j]);
	}
	}

	lengths[i] = localMax + 1;
	ans = Math.max(ans, lengths[i]);
	}

	return ans;
	}
	}

view raw lengthOfLIS.java hosted with ❤ by GitHub

kotlin
Time complexity O(n^2)

	class Solution {
	fun lengthOfLIS(nums: IntArray): Int {
	val dp = IntArray(nums.size) { 1 }
	var ans = Int.MIN_VALUE

	for(i in 0..nums.lastIndex) {
	for(j in 0 until i) {
	if(nums[j] < nums[i]) {
	if(dp[j] + 1 > dp[i]) {
	dp[i] = dp[j] + 1
	}
	}
	}
	ans = Math.max(ans, dp[i])
	}

	return ans
	}
	}

另一種想法，使用binary search，可以把時間複雜度降到 O(nlogn)

用一個額外的 list，紀錄目前最長的 subsequence，初始值是 nums[0]

當 nums[i] 大於 list 的最後一個數字時，直接加到 list 中，因為符合題意，是升冪

當 nums[i] 小於等於 list 的第一個數字時，直接取代第一個數字

為什麼可以這樣做呢？

首先，因為我們是按順序歷遍，當在 nums[i] 遇到一個比list 的第一個數字小的值

代表從位置 i 開始，有可能有機會找到一個新的 increasing subsequence

且取代第一個數字，並不會增加現有長度，也就是目前的最大值並沒有變化

至於之後出現更大的值後，會不會出現例外

這時候就是使用 binary search 的時候了，用 [4,10,4,3,8,9] 來舉例

到 i = 2 的時候，list = [4,10]

i = 3 時，list = [3,10]，可以看到長度並沒有變

i = 4 時，3 < nums[4] = 8 <= 10，這時候用 binary search 找到第一個不小於 8 的位置

然後取代變成 8，所以list會變成 [3,8]

i = 5 時，list = [3,8,9]

最後的 list.size 就是答案

有一個要注意的地方是，list 裡面的 subsequence 並不會是正確的 subsequence

因為題目是要求長度，所以可以用這種方式

舉例，當 nums = [4,5,6,3]，最後的 list = [3,5,6]，長度是對的，但 subsequence 是錯的

kotlin

	class Solution {
	fun lengthOfLIS(nums: IntArray): Int {
	val ans = arrayListOf<Int>()
	ans.add(nums[0])

	for(i in 1..nums.lastIndex) {
	var left = 0
	var right = ans.size

	while(left < right) {
	val mid = left + (right - left) / 2
	if(ans[mid] < nums[i]) {
	left = mid + 1
	} else {
	right = mid
	}
	}

	if(right >= ans.size) {
	ans.add(nums[i])
	} else {
	ans[right] = nums[i]
	}
	}

	return ans.size
	}
	}

About Software