C++ Simple Intuitive DP with Full explaination | Tabulation | O(N) | Single Traversal
Intuition\n Describe your first thoughts on how to solve this problem. \nWe keep track of what is the current non-decreasing subarray length throug a 2D DP of s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe keep track of what is the current non-decreasing subarray length throug a 2D DP of size (n X 2) which stores the current non-decreasing subarray length with nums1 element as the last number and nums2 element as the last number (DP has 2 rows). Now we can calculate the non-decreasing subarray length of the next element using the information of the previous element. We maintain an ans variable to store the maximum subarray length.It takes only single traversal.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(2*n)$$\n\n\n\nStay updated for a space optimized solution to be posted soon.\n\n# Code\n```\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {\n        int n = nums1.size();\n        if(n == 1)\n            return 1;\n        int ans = 0;\n        vector<vector<int>> dp(n+1,vector<int> (2,1));\n\n        for(int i=1;i<n;i++)\n        {\n            if(nums1[i]>= nums1[i-1])\n            {\n                dp[i][0] = max(dp[i][0],dp[i-1][0] + 1);\n            }\n            if(nums1[i] >= nums2[i-1])\n            {\n                dp[i][0] = max(dp[i][0],dp[i-1][1] +1);\n            }\n            if(nums2[i]>= nums1[i-1])\n            {\n                dp[i][1] = max(dp[i][1],dp[i-1][0] + 1);\n            }\n            if(nums2[i]>= nums2[i-1])\n            {\n                dp[i][1] = max(dp[i][1],dp[i-1][1] + 1);\n            }\n            ans = max(ans,max(dp[i][0],dp[i][1]));\n        }\n        return ans;\n    }\n};\n```
['Array', 'Dynamic Programming', 'C++']