DEV Community

Tim-Wu-330
Tim-Wu-330

Posted on

Dp Algo

2771. Longest Non-decreasing Subarray From Two Arrays

Image description

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 1
        Len = len(nums1)
        dp1 = [1] * Len
        dp2 = [1] * Len
        for i in range(1, Len):
            if nums1[i] >= nums1[i-1]:
                dp1[i] = max(dp1[i], dp1[i-1] + 1)
            if nums1[i] >= nums2[i-1]:
                dp1[i] = max(dp1[i], dp2[i-1]+  1)
            if nums2[i] >= nums2[i-1]:
                dp2[i] = max(dp2[i-1] + 1, dp2[i])
            if nums2[i] >= nums1[i-1]:
                dp2[i] = max(dp2[i], dp1[i-1] + 1)
            ans = max(ans, dp1[i], dp2[i])
        # print(dp1, dp2)
        return ans
Enter fullscreen mode Exit fullscreen mode

Top comments (0)