dfs + dp, O(n) time and space
Code\n\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n\n        @cache\n        def dfs(index, choice):\n\n
# Code\n```\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n\n        @cache\n        def dfs(index, choice):\n\n            # base case, we reached the end\n            if index == len(nums1) - 1:\n                return 1            \n            \n            # if we were asked to choose nums1[index] at this index\n            if choice == 1:\n                res = 1\n                if nums1[index] <= nums1[index + 1]:\n                    res = max(res, 1 + dfs(index + 1, 1))\n                if nums1[index] <= nums2[index + 1]:\n                    res = max(res, 1 + dfs(index + 1, 2))\n                return res\n\n            # if we were asked to choose nums2[index] at this index\n            if choice == 2:\n                res = 1\n                if nums2[index] <= nums1[index + 1]:\n                    res = max(res, 1 + dfs(index + 1, 1))\n                if nums2[index] <= nums2[index + 1]:\n                    res = max(res, 1 + dfs(index + 1, 2))\n                return res\n\n            # in either case, the minimum non-decreasing subarray we could get from that point was length 1\n            # if the following indices were possible to continue the non-decreasing subarray, we try\n        \n        # call dfs\n        res = 1\n        for i in range(len(nums1)):\n            res = max(res, dfs(i, 1))\n            res = max(res, dfs(i, 2))\n        return res\n```
['Python3']