DP solution || Clearly Explained || T/M: 92.7% / 98.6%
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen initially approaching this problem, consider these key points.\n\n- You can choose
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen initially approaching this problem, consider these key points.\n\n- You can choose from two different arrays at each step.\n- A non-decreasing subarray means each element is equal to or larger than the preceding element.\n- Your choice at index `i` will affect the potential length of the non-decreasing subarray that ends at index `i + 1`.\n\nGiven these, dynamic programming would be the go-to strategy for this problem because in every index, every decision is made based on earlier decisions. Hence, it efficiently navigates through overlapping choices at each step and builds upon smaller, proviously solved protions to find the optimal, to ensure optimal decisions made at every index by reusing earlier calculations.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n## Dynamic programming setup:\n\nState Definition:\n\n- `dp1[i]`: Represents the length of the longest non-decreasing subarray ending at index i when the element from nums1[i] is chosen.\n- `dp2[i]`: Represents the length of the longest non-decreasing subarray ending at index i when the element from nums2[i] is chosen.\n\nBase Case:\n\n- At index `0`, there are no previous elements to compare with, so the longest non-decreasing subarray for both `dp1` and `dp2` is simply the first element itself.\n- `dp1[0] = 1`\n- `dp2[0] = 1`\n\nRecursive relation:\n\nFor each `i`:\n\n1. For `dp1[i]`\n    - If `nums1[i]` is non-decreasing with respect to both `nums1[i-1]` and `nums2[i-1]`, then `dp1[i]` is the maximum length of either subarray up to i-1 plus one.\n    - If `nums1[i]` is non-decreasing only with respect to `nums1[i-1]`, then `dp1[i]` extends the subarray from `nums1` only.\n    - If `nums1[i]` is non-decreasing only with respect to `nums2[i-1]`, then `dp1[i]` extends the subarray from `nums2` only.\n    - If `nums1[i]` is not non-decreasing with respect to either, we start a new subarray, so `dp1[i]` is reset to 1.\n\n            if nums1[i] >= nums1[i - 1] and nums1[i] >= nums2[i - 1]:\n                curr1 = max(prev_curr1 + 1, prev_curr2 + 1)\n            elif nums1[i] >= nums1[i - 1]:\n                curr1 = prev_curr1 + 1\n            elif nums1[i] >= nums2[i - 1]:\n                curr1 = prev_curr2 + 1\n            else:\n                curr1 = 1\n\n2. For `dp2[i]`\n    - Similar rules applied.\n\n            if nums2[i] >= nums1[i - 1] and nums2[i] >= nums2[i - 1]:\n                curr2 = max(prev_curr1 + 1, prev_curr2 + 1)\n            elif nums2[i] >= nums2[i - 1]:\n                curr2 = prev_curr2 + 1\n            elif nums2[i] >= nums1[i - 1]:\n                curr2 = prev_curr1 + 1\n            else:\n                curr2 = 1\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$ for space-optimized code as below.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n        # dp1[i] = longest non-decreasing subarray ending at i with nums1[i]\n        # dp2[i] = longest non-decreasing subarray ending at i with nums2[i]\n\n        n = len(nums1)\n        curr1 = 1\n        curr2 = 1\n        ans = 1\n        for i in range(1, n):\n\n            prev_curr1 = curr1\n            prev_curr2 = curr2\n\n            if nums1[i] >= nums1[i - 1] and nums1[i] >= nums2[i - 1]:\n                curr1 = max(prev_curr1 + 1, prev_curr2 + 1)\n            elif nums1[i] >= nums1[i - 1]:\n                curr1 = prev_curr1 + 1\n            elif nums1[i] >= nums2[i - 1]:\n                curr1 = prev_curr2 + 1\n            else:\n                curr1 = 1\n            \n            if nums2[i] >= nums1[i - 1] and nums2[i] >= nums2[i - 1]:\n                curr2 = max(prev_curr1 + 1, prev_curr2 + 1)\n            elif nums2[i] >= nums2[i - 1]:\n                curr2 = prev_curr2 + 1\n            elif nums2[i] >= nums1[i - 1]:\n                curr2 = prev_curr1 + 1\n            else:\n                curr2 = 1\n            ans = max(ans, curr1, curr2)\n\n        return ans\n\n```
['Dynamic Programming', 'Python', 'Python3']