Problem statement

https://binarysearch.com/problems/Odd-Longest-Increasing-Subsequence/

Solution

We can use dp with states (current index we traverse, number of odd numbers we still need, previous number was taken).

  1. If i >= n, it means that we reached the end, if k = 0, we are happy, we do not need more odd numbers, if k > 0, we return minus infinity.
  2. We can have one/two options: either take or not take new number: we can take it only if it is bigger than prev.

Complexity

It is O(n^2 * k) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        @lru_cache(None)
        def dp(i, k, prev):
            if i >= n: return -k*10**9
            cands = [dp(i + 1, k, prev)]
            if nums[i] > prev:
                k2 = max(0, k - 1) if nums[i] % 2 else k
                cands += [dp(i + 1, k2, nums[i]) + 1]
            return max(cands)

        return max(0, dp(0, k, -10**9))