BinarySearch 0168 Longest Contiguously Strictly Increasing Sublist After Deletion

Problem statement

https://binarysearch.com/problems/Longest-Contiguously-Strictly-Increasing-Sublist-After-Deletion/

Solution

Let dp0[i] is be the answer for s[:i+1], where we do not delete any elements and dp1[i], where we delete one element. Then we can update values for i if we know for i - 1. Notice, that dp1[0] = 0, because when we delete one element, there will be 0 elements.

Complexity

It is O(n) for time and space. Space can be made O(1).

Code

class Solution:
    def solve(self, nums):
        if not nums: return 0
        n = len(nums)
        dp0 = [1]*n
        dp1 = [0] + [1]*(n-1)

        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                dp0[i] = 1 + dp0[i - 1]
                dp1[i] = 1 + dp1[i - 1]
            if i > 1 and nums[i] > nums[i - 2]:
                dp1[i] = max(dp1[i], dp0[i-2] + 1)

        return max(max(dp0), max(dp1))