Easy To Understand DP | Top-Down -> Bottom-Up | Python
This solution runs in O(n) time, but it will be slower than other DP solution due to trading off the hidden constants for easier understanding.\n\nWe know that 
This solution runs in `O(n)` time, but it will be slower than other DP solution due to trading off the hidden constants for easier understanding.\n\nWe know that for each index i, we need to make a decision and choose either nums1[i] or nums2[i] such that our choice yields the most optimal solution. So we must keep track of a few things:\n* which index i we are currently at\n* the previous integer that was chosen (so that we can make sure that our current choice for index i is non-decreasing)\n* Whether or not we want to choose the current index i as our starting value for our longest non-decreasing subarray (since the most optimal solution might start with the middle index as the start for our subarray)\n\nFor the first bullet point, we must have a variable i to keep track of the index for our top-down solution.\nBut for the second and third bullet points, we can just use booleans to keep track.\n\nWe know that at index i, the previous integer that was chosen must be at index i-1, but we don\'t know if it was the integer at index i-1 in `nums1` or `nums2`. So we can use a boolean to keep track of this instead of an an entire integer, which would blow up our time complexity.\n\nAnd we just need one boolean to keep track of whether or not we have started counting for our subarray, since if the optimal solution starts at the middle index, we do not want to start counting and checking for the non-decreasing constraint when we haven\'t reached the start of where the optimal solution would start at.\n\nWe can cache the return values with `@cache`, and so our top-down recursive solution looks like the code below:\n```\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n        @cache\n        def dp(i, isInNums1, startedCounting):\n            if i == len(nums1):\n                return 0\n            # the previous value used is -infinity if i == 0 (since there is no value before index 0) or if we have not started counting for our subarray yet\n            # otherwise, the previous value is at index i-1 of the array specified by isInNums1\n            prev = float(\'-inf\') if i == 0 or not startedCounting else nums1[i-1] if isInNums1 else nums2[i-1]\n            ret = 0\n\n            # If we have not started counting yet, we should consider not starting\n            # at index i but possibly at index i+1\n            if not startedCounting:\n                ret = max(ret, dp(i+1, True, False))\n\n            # if the current number satisfies the non-decreasing constraint, then\n            # add 1 and recurse to the next index at i+1, making sure that we mark the\n            # correct boolean for isInNums1, and since we started counting for our\n            # subarray by taking the integer at index i, startedCounting must be set to True\n            if nums1[i] >= prev:\n                ret = max(ret, 1+dp(i+1, True, True))\n            if nums2[i] >= prev:\n                ret = max(ret, 1+dp(i+1, False, True))\n\n            return ret\n\n        return dp(0, True, False)\n```\nWe can convert this to bottom-up by using a for loop for i, and nested for loops for every possible boolean combination of `isInNums1` and `startedCounting`. The for loop for i starts at the base case value `i == len(nums1)` and decrements from there. The rest of the code within the for loops is essentially the same as the top-down solution.\n```\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n        n = len(nums1)\n        dp = [[[0]*2 for _ in range(2)] for _ in range(n+1)]\n        for i in range(n, -1, -1):\n            for isInNums1 in (False, True):\n                for startedCounting in (False, True):\n                    if i == n:\n                        dp[i][isInNums1][startedCounting] = 0\n                    else:\n                        # the previous value used is -infinity if i == 0 (since there is no value before index 0) or if we have not started counting for our subarray yet\n                        # otherwise, the previous value is at index i-1 of the array specified by isInNums1\n                        prev = float(\'-inf\') if i == 0 or not startedCounting else nums1[i-1] if isInNums1 else nums2[i-1]\n                        ret = 0\n\n                        # If we have not started counting yet, we should consider not starting\n                        # at index i but possibly at index i+1\n                        if not startedCounting:\n                            ret = max(ret, dp[i+1][True][False])\n\n                        # if the current number satisfies the non-decreasing constraint, then\n                        # add 1 and recurse to the next index at i+1, making sure that we mark the\n                        # correct boolean for isInNums1, and since we started counting for our\n                        # subarray by taking the integer at index i, startedCounting must be set to True\n                        if nums1[i] >= prev:\n                            ret = max(ret, 1+dp[i+1][True][True])\n                        if nums2[i] >= prev:\n                            ret = max(ret, 1+dp[i+1][False][True])\n                        dp[i][isInNums1][startedCounting] = ret\n        return dp[0][True][False]\n```\n\nTime Complexity: `O(n)` since variable i has `len(nums1)` different possible values, `isInNums1` has 2 possible values, and `startedCounting` has 2 possible values, which yields a time complexity of `O(4n)` = `O(n)`.\nSpace Complexity: `O(n)` for similar reasons (technically `O(4n)` as well)
['Dynamic Programming']