Quiz: LIS Basics

What is the recurrence relation for LIS with dp[i] = length of LIS ending at index i?

1. A.dp[i] = min(dp[j]) for all j < i
2. B.dp[i] = dp[i-1] + 1
3. C.dp[i] = dp[i-1] if arr[i] > arr[i-1]
4. D.dp[i] = max(dp[j]) + 1 for all j < i where arr[j] < arr[i]