C++ | Very Simple & Intuitive DP | Well Explained and Commented
Intuition\n Describe your first thoughts on how to solve this problem. \nBasically, we can check by putting the current element nums3[i] both as nums1[i] or num
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasically, we can check by putting the current element nums3[i] both as nums1[i] or nums2[i].\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe are using 2 dp arrays. dp1[i] tells the max length of subarray ending at index i considering that nums3[i] = nums1[i]. Similarly dp2[i] tells the max length of subarray ending at index i conidering that nums3[i] = nums2[i].\nFor each index 1 to n-1, we will check both the possibilities.\nWe can choose the previous element either as nums1[i-1] or nums2[i-1] if they are less than equal to currently chosen value coz we need to find the non decreasing subarray. (We are checking only the immediate previous because this is subarray not subsequence).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {\n        int n = nums1.size();\n        vector<int> dp1(n,1),dp2(n,1);\n        int ans = 1;\n        \n        //dp1[i] tells the max length of subarray ending at index i considering that nums3[i] = nums1[i]. \n        //Similarly dp2[i] tells the max length of subarray ending at index i conidering that nums3[i] = nums2[i]\n\n        for(int i = 1;i<n;i++)\n        {\n            //if we make nums3[i] = nums1[i] then what max ans can we get\n            if(nums1[i-1]<=nums1[i]) dp1[i] = max(dp1[i],1+dp1[i-1]);\n            if(nums2[i-1]<=nums1[i]) dp1[i] = max(dp1[i],1+dp2[i-1]);\n            \n            //if we make nums3[i] = nums2[i] then what max ans can we get\n            if(nums2[i-1]<=nums2[i]) dp2[i] = max(dp2[i],1+dp2[i-1]);\n            if(nums1[i-1]<=nums2[i]) dp2[i] = max(dp2[i],1+dp1[i-1]);\n            \n            ans = max({ans,dp1[i],dp2[i]}); //final ans will be max length possible of any subarray\n        }\n        return ans;\n    }\n};\n```\nPlease Upvote if you understood the solution and found it intuitive.\n\nIf you have any doubts, feel free to ask in comments.
['Dynamic Programming', 'C++']