Solving Maximum Length of Non-Decreasing Subsequences using DP
Finding the Maximum Length of Non-Decreasing Subsequences\n\n## Overview\n\nThis article explains a solution to find the maximum length of a non-decreasing subs
# Finding the Maximum Length of Non-Decreasing Subsequences\n\n## Overview\n\nThis article explains a solution to find the maximum length of a non-decreasing subsequence from two lists of integers. The approach uses dynamic programming to handle the problem efficiently.\n\n## Problem Statement\n\nGiven two lists, `nums1` and `nums2`, of the same length, the task is to determine the maximum length of a non-decreasing subsequence that can be formed by choosing elements from either `nums1` or `nums2` while maintaining the order of indices.\n\n## Approach\n\nThe solution uses dynamic programming to keep track of the maximum length of non-decreasing subsequences that end with elements from `nums1` and `nums2`. \n\n### Dynamic Programming Table\n\nWe define a 2D array `dp` where:\n- `dp[i][0]` represents the maximum length of a non-decreasing subsequence ending with `nums1[i]`.\n- `dp[i][1]` represents the maximum length of a non-decreasing subsequence ending with `nums2[i]`.\n\n### Initialization\n\nThe table `dp` is initialized as follows:\n- Each entry in `dp` starts with a value of `1` because a single element alone is a valid non-decreasing subsequence.\n\n### Transition\n\nFor each index `i` from `1` to `n-1`, the table is updated based on the following conditions:\n- **For `dp[i][0]`** (ending with `nums1[i]`):\n  - If `nums1[i] >= nums1[i-1]`, then `dp[i][0]` can be extended from `dp[i-1][0]`.\n  - If `nums1[i] >= nums2[i-1]`, then `dp[i][0]` can also be extended from `dp[i-1][1]`.\n- **For `dp[i][1]`** (ending with `nums2[i]`):\n  - If `nums2[i] >= nums1[i-1]`, then `dp[i][1]` can be extended from `dp[i-1][0]`.\n  - If `nums2[i] >= nums2[i-1]`, then `dp[i][1]` can also be extended from `dp[i-1][1]`.\n\nAfter processing each index `i`, the maximum length found so far is updated.\n\n\n# Code\n```\nfrom typing import List\n\nclass Solution:\n    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:\n        if not nums1 or not nums2:\n            return 0\n        n = len(nums1)\n        if n == 1:\n            return 1\n        \n        # dp[i][0] - max length of non-decreasing sequence ending with nums1[i]\n        # dp[i][1] - max length of non-decreasing sequence ending with nums2[i]\n        dp = [[1] * 2 for _ in range(n)]\n        maxlen = 1\n        \n        for i in range(1, n):\n            # Check if nums1[i] can continue a sequence ending with nums1[i-1]\n            if nums1[i] >= nums1[i-1]:\n                dp[i][0] = dp[i-1][0] + 1\n            # Check if nums1[i] can continue a sequence ending with nums2[i-1]\n            if nums1[i] >= nums2[i-1]:\n                dp[i][0] = max(dp[i][0], dp[i-1][1] + 1)\n            \n            # Check if nums2[i] can continue a sequence ending with nums1[i-1]\n            if nums2[i] >= nums1[i-1]:\n                dp[i][1] = dp[i-1][0] + 1\n            # Check if nums2[i] can continue a sequence ending with nums2[i-1]\n            if nums2[i] >= nums2[i-1]:\n                dp[i][1] = max(dp[i][1], dp[i-1][1] + 1)\n            \n            # Update the maximum length found so far\n            maxlen = max(maxlen, dp[i][0], dp[i][1])\n        \n        return maxlen\n\n```
['Python3']