https://www.acmicpc.net/problem/1965
initial
I initially thought you didn't need DP and DP was just to make it more efficient. I used a nested for loop and for a given element, I checked other elements from the back of the list and if they were smaller than our given element, we increase count and set tmp as that value lst[j].
my wrong code:
n = int(input())
lst = list(map(int, input().split()))
ans = [0 for _ in range(n)]
for i in range(n):
tmp = int(10e6)
count = 1
for j in range(i - 1, -1, -1):
if lst[i] > lst[j] and lst[j] < tmp:
tmp = lst[j]
count += 1
ans[i] = count
print(max(ans))but let's look at where it can be wrong for a given test case. look at
7
10 22 9 33 21 50 41
My wrong code will give 3 instead of correct 4 because it does not guarantee the correct result for finding the LIS because it doesn't consider the entire sequence and its possible combinations.
For example, at 33, we traverse back and find 9. We set tmp as 9 but 10 , 22 are the better subsequence to make the length 3 for 33 (10 22 33). So my code is limited. So we need to account the previous combination of subsequence by traversing from the front and using a dp.
solution
n = int(input())
lst = list(map(int, input().split()))
dp = [1] * n # Initialize an array to store the length of LIS ending at each index.
for i in range(1, n):
for j in range(i):
if lst[i] > lst[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
max_lis_length = max(dp)
print(max_lis_length)or
n = int(input())
lst = list(map(int, input().split()))
ans = [0 for _ in range(n)]
def lis(nums):
n = len(nums)
if n == 0:
return 0 # Empty list has an LIS of 0.
# Initialize an array to store the length of LIS ending at each index.
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
val = lis(lst)
print(val)complexity
n^2 time and n space
