Short Video with detail explanation 🔥 || C++ || Easy DP Solution O(N) 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nUse 2 dp arrays to solve.\n\nYou can refer youtube video for better understanding\n\nht
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse 2 dp arrays to solve.\n\nYou can refer youtube video for better understanding\n\nhttps://youtu.be/0OAEqtptggs\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo solve the above problem, we required to 2 dp arrays. Every element is dependent only on previous element\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(N)\n```C++ []\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& v1, vector<int>& v2) {\n        int n=v1.size();\n        vector<int>dp1(n,1);\n        vector<int>dp2(n,1);\n        int ans=1;\n        for(int i=1;i<n;i++)\n        {\n            if(v1[i]>=v1[i-1])\n                dp1[i]=max(dp1[i],1+dp1[i-1]);\n            if(v1[i]>=v2[i-1])\n                dp1[i]=max(dp1[i],1+dp2[i-1]);\n            if(v2[i]>=v1[i-1])\n                dp2[i]=max(dp2[i],1+dp1[i-1]);\n            if(v2[i]>=v2[i-1])\n                dp2[i]=max(dp2[i],1+dp2[i-1]);\n            ans=max(ans,max(dp1[i],dp2[i]));\n        }\n        return ans;\n    }\n};\n```\n```JAVA []\nimport java.util.*;\n\nclass Solution {\n    public int maxNonDecreasingLength(List<Integer> v1, List<Integer> v2) {\n        int n = v1.size();\n        int[] dp1 = new int[n];\n        int[] dp2 = new int[n];\n        int ans = 1;\n        \n        Arrays.fill(dp1, 1);\n        Arrays.fill(dp2, 1);\n        \n        for (int i = 1; i < n; i++) {\n            if (v1.get(i) >= v1.get(i - 1))\n                dp1[i] = Math.max(dp1[i], 1 + dp1[i - 1]);\n            if (v1.get(i) >= v2.get(i - 1))\n                dp1[i] = Math.max(dp1[i], 1 + dp2[i - 1]);\n            if (v2.get(i) >= v1.get(i - 1))\n                dp2[i] = Math.max(dp2[i], 1 + dp1[i - 1]);\n            if (v2.get(i) >= v2.get(i - 1))\n                dp2[i] = Math.max(dp2[i], 1 + dp2[i - 1]);\n            ans = Math.max(ans, Math.max(dp1[i], dp2[i]));\n        }\n        \n        return ans;\n    }\n}\n```\n```Python []\nclass Solution:\n    def maxNonDecreasingLength(self, v1, v2):\n        n = len(v1)\n        dp1 = [1] * n\n        dp2 = [1] * n\n        ans = 1\n\n        for i in range(1, n):\n            if v1[i] >= v1[i - 1]:\n                dp1[i] = max(dp1[i], 1 + dp1[i - 1])\n            if v1[i] >= v2[i - 1]:\n                dp1[i] = max(dp1[i], 1 + dp2[i - 1])\n            if v2[i] >= v1[i - 1]:\n                dp2[i] = max(dp2[i], 1 + dp1[i - 1])\n            if v2[i] >= v2[i - 1]:\n                dp2[i] = max(dp2[i], 1 + dp2[i - 1])\n            ans = max(ans, max(dp1[i], dp2[i]))\n        \n        return ans\n\n```
['Array', 'Dynamic Programming', 'C++']