Last updated
Was this helpful?
Last updated
Was this helpful?
O(n^2)
ๅพๅ้กๅฏไปฅ็ๅบไพ, ่ฆๆพๅฐๆ้ท้ๅขๅญๅบๅ
ไธๅฎๆๅบๆผๅ้ข็็ๆ
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j]+1)
}
ๅๅง็ๆ ๏ผ
dp[i] ๆๆๅ ็ด ็ฝฎ 1๏ผๅซ็พฉๆฏๆฏๅๅ ็ด ้ฝ่ณๅฐๅฏไปฅๅฎ็จๆ็บๅญๅบๅ๏ผๆญคๆ้ทๅบฆ้ฝ็บ 1ใ
ๆไปฅ j ่ฆๅจ i ๅ้ข, nums[i] > nums[j]
time: O(n^2)
space: O(n)
time: O(nlogn)
space: O(n)
Given an array nums[]
, return the length of the longest increasing subsequence (LIS).
The brute-force or DP approach is O(n2)O(n^2)O(n2). But this solution runs in O(nlogโกn)O(n \log n)O(nlogn) using binary search.
Maintain a list dp
, where:
dp[i]
is the smallest possible tail of an increasing subsequence of length i + 1
.
Letโs say we build subsequences ending at:
This means:
We have an increasing subsequence of length 3 ending with 9
If a new number 6
comes in, we could replace 9
with 6
(making it easier to extend future subsequences)
So the idea is: always keep dp
as optimized as possible, replacing with smaller values if we can.
dp.add(nums[0]);
Start with the first number โ weโve found a subsequence of length 1.
nums[i]
:If itโs smaller than everything so far:
โ Replace the first element (start new possible LIS).
If it's larger than the last element:
โ Extend the LIS.
Otherwise:
โ Find the first element in dp
greater than or equal to nums[i]
and replace it to keep the sequence tail as small as possible.
binarySearch(dp, num)
Your version of binarySerach()
is slightly more complicated than necessary.
The goal is to find the first element โฅ num.
Hereโs a cleaner and more standard version:
This returns the leftmost index where dp.get(index) >= num
, which is what we want to replace.
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Step-by-step dp
:
Final dp.size() = 4
, so LIS = 4.
dp
doesn't store an actual LIS, just helps track the length.
The trick is: we only replace, never remove โ the dp
list is always valid.
Let me know if youโd like to adapt this code to recover the actual LIS sequence, or if you want a visual animation of how it builds!
4o
You said:
but seems 2, 3, 7, 18 is a LIS?
ChatGPT said:
Yes! You're absolutely right โ in the example:
One possible Longest Increasing Subsequence (LIS) is:
And that's exactly what the algorithmโs dp
ends up with at the end:
The dp
list does not always represent an actual LIS from the array, but:
It always maintains a list such that:
Its length equals the length of the LIS,
And the values are the smallest possible ending values for increasing subsequences of various lengths.
The real LIS might use different elements from the original array โ this greedy + binary search method only gives you the length, not necessarily the actual sequence.
In this case, dp = [2, 3, 7, 18]
does happen to be a valid LIS, but:
Thatโs a coincidence โ it won't always reconstruct the actual sequence.
It's just a helpful structure to find the length efficiently in O(nlogโกn)O(n \log n)O(nlogn).
Step-by-step dp
:
3
โ [3]
5
โ [3, 5]
7
โ [3, 5, 7]
1
โ [1, 5, 7] โ replaced 3 with 1
2
โ [1, 2, 7]
8
โ [1, 2, 7, 8]
Final dp = [1, 2, 7, 8]
LIS length = 4 โ
But [3, 5, 7, 8]
is also a valid LIS โ dp
doesn't give the original one.
Yes, in your case dp = [2, 3, 7, 18]
is a valid LIS.
But thatโs not guaranteed โ dp
is a tool to get the LIS length, not necessarily the actual sequence.
Would you like to see how to recover the actual LIS in O(nlogโกn)O(n \log n)O(nlogn)?
dp[0] means length 1's ็ตๅฐพๆๅฐ็ LIS
dp[1] means length 2 ็ตๅฐพๆๅฐ็ LIS
O(n^2)