Python 3 - Dynamic Programming + Explanation
We need to keep two arrays that constitute the longest path if we choose either nums1 or nums2 for each i in the range(1, n). Rather than storing the actual num
We need to keep two arrays that constitute the longest path if we choose either `nums1` or `nums2` for each `i` in the `range(1, n)`. Rather than storing the actual numbers chosen, we can just keep track of how long that longest path is, this is what we store in `dp1` and `dp2`, where each represents the length ending at `i` if we choose `nums1[i]` or `nums2[i]` respectively.\n\nWe have to update both `dp` arrays for each `i`, where we ask ourselves: "could we continue the longest decreasing subsequence by staying on the current `nums` (`a` and `b` in the method `__calculate_dp` can represent either `1` or `2`, depending on the way they are passed in to the method), or could we switch over from the other `nums` and form a longer subsequence?".\n\nAt the end of each iteration, we update `max_length` with the new longest path value.\n```\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n        n = len(nums1)\n\n        # Initialize DP arrays to store the length of the non-decreasing subarray at index i.\n        # dp1[i] represents the length ending at i using nums1[i]\n        # dp2[i] represents the length ending at i using nums2[i]\n        dp1 = [1] * n\n        dp2 = [1] * n\n\n        max_length = 1\n\n        for i in range(1, n):\n            Solution.__calculate_dp(nums1, nums2, dp1, dp2, i)\n            Solution.__calculate_dp(nums2, nums1, dp2, dp1, i)\n            \n            max_length = max(max_length, dp1[i], dp2[i])\n\n        return max_length\n\n    @staticmethod\n    def __calculate_dp(\n        nums_a: List[int],\n        nums_b: List[int],\n        dp_a: List[int],\n        dp_b: List[int],\n        i: int\n    ) -> None:\n        """\n        For each stage of the iteration, at index i we ask ourselves could we continue\n        the longest decreasing subsequence by staying on nums_a or switching over from nums_b?\n        """\n        # If we stay on nums_a, is it still a non-decreasing subarray.\n        if nums_a[i] >= nums_a[i - 1]:\n            dp_a[i] = dp_a[i - 1] + 1\n\n        # If we were to swap over to nums_a from nums_b and have it still form a non-decreasing subarray,\n        # would this be a longer subarray than if we had stayed on nums_a?\n        if nums_a[i] >= nums_b[i - 1]:\n            dp_a[i] = max(dp_a[i], dp_b[i - 1] + 1)\n```
['Python3']