[백준] 12015번: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

initial

I tried solving via DP but runtime.

Since element of length 1 itself is considered a subsequence, I initialised dp of value 1 for each element and through a nested for loop, if the current value is bigger than the previous values to be iterated, we add +1 to dp[i] and record the max value via max(dp[j]+1, dp[i])

n = int(input())
lst = list(map(int, input().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

solution

https://jainn.tistory.com/90
https://seungkwan.tistory.com/8

You can use binary search to make it more efficient. Go to those links but general approach is when we have an incoming value that is greater than the recorded value, we can just append at the end of our recorded list. But if it is smaller, we want to find the index where we can put this value in our recorded list.

ans[left] = i eihter updates value in recorded list or extends the recorded list. like this I didnt know

n = int(input())
lst = list(map(int, input().split()))
ans = [lst[0]]

for i in lst[1:]:
    if i > ans[-1]:
        ans.append(i)
    else:
        left, right = 0, len(ans) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            if i > ans[mid]:
                left = mid + 1
            else:
                right = mid
        
        ans[left] = i

print(len(ans))

complexity

o n log n time and n space cuz of ans list?

The given code is an implementation of the Longest Increasing Subsequence (LIS) problem using binary search to optimize the solution. The code finds the length of the LIS for a given list lst. Here's the complexity analysis:

• Let n be the length of the input list lst.

1. Initializing ans takes O(1) time.
2. The main loop iterates through each element in lst once, which takes O(n) time.
3. Inside the loop, there's a binary search to find the correct position to update ans. Binary search takes O(log(n)) time.
4. Updating ans or appending an element to ans takes O(1) time.

The overall time complexity of the code is O(n * log(n)), where n is the length of the input list.

The space complexity is O(n) because the ans list stores at most n elements.

This code efficiently finds the length of the Longest Increasing Subsequence in a given list by using binary search for each element, resulting in a time complexity of O(n * log(n)).