the most efficient possible solution to this problem, c++, beats 100, 100
Intuition\n Describe your first thoughts on how to solve this problem. \nstruggled a bit and fell into the memoization trap but realized that this would be inne
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nstruggled a bit and fell into the memoization trap but realized that this would be inneficient because we\'d have to cache two states which would lead to fewer redundant recursive branches occuring. I think once I realized that the maxIncreasingSubarray(pos...n-1) depended on the numbers we\'d chosen before and what numbers we would choose after, thats when i realized that memo wasn\'t the play.\n\nI for sure spent some time going down the "pick num1, pick num2" 0-1 knapsack type memoization problem, and then just return the result and memoize at the index i in range(1, n-1). \n\ninstead, ive encountered problems with similar patterns before, this is a pattern that ive internalized relatively well, so i built a recurrence relation just using two different arrays and it worked out...\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\niterate from 1 -> n-1: lets say we are at index \'i\' in this iteration...\n\np1 is the length of the previous nondecreasing subarray had we chosen nums1[i-1] to be in our combined array\n\np2 is the length of the previous nondecreasing subarray had we chosen nums2[i-1] to append to our combined array\n\nwith p1 and p2, the solution is relatively straightforward, you kinda just have to build a reccurrence relation and trust that itll work in order to solve the problem fast lol thats dp. tricky problem though for sure a hard-medium \n \nif nums1[i] >= nums1[i-1], then we can append nums1[i] to the back of the "p1" subarray\n\nif nums1[i] >= nums2[i-1], then we can append nums2[i] to the back of the "p1" subarray (note: even though we are comparing with nums2, we are still choosing a number from nums1, and remember p1 will be representative of us having choosen nums1[i-1] to append to our subarray on the next iteration)\n\n... repeat same steps with nums2[i] (see code below)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(n) just one pass\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) is more intuitive with two arrays(thats the solution i started with), O(1) is optimized solution below\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {\n        int n = nums1.size(); \n        int p1 = 1; \n        int p2 = 1;\n        int res = 1;\n        for(int i = 1; i < n; i++) { \n            int maxSeqLen1 = 1, maxSeqLen2 = 1;\n\n            int num1 = nums1[i], num2 = nums2[i];\n\n            if(num1 >= nums1[i-1]) maxSeqLen1 = p1+1;\n\n            if(num1 >= nums2[i-1]) maxSeqLen1 = maxSeqLen1 > p2+1 ? maxSeqLen1 : p2+1;\n\n            if(num2 >= nums1[i-1]) maxSeqLen2 = p1+1;\n\n            if(num2 >= nums2[i-1]) maxSeqLen2 = maxSeqLen2 > p2+1 ? maxSeqLen2 : p2+1;\n\n            p1 = maxSeqLen1;\n            p2 = maxSeqLen2;\n            int m1 = p1 > p2 ? p1 : p2; \n            res = res > m1 ? res : m1;\n        }\n        return res;\n    }\n};\n```
['C++']