DP: bottom-up linear solution explained
Intuition\nWas a medium on a weekly contest as a third task. At first I tried to solve it using naive approach. By the definition of the task you need to choose
# Intuition\nWas a medium on a weekly contest as a third task. At first I tried to solve it using naive approach. By the definition of the task you need to choose i-th item from two arrays.\n\nGiven examples are quite poor, so after drawing more complex examples it was clear that at each point selecting min or max may increase the length of the prefix or the suffix, so there is some kind of variation. However, naive approach to iterate from left to right with selecting $min >= last$ or just min if there none >= last, as well as iterate from right to left selecting $max <= last$ or just max if there none <= last didn\'t really work well. \n\nWhen there were 5 minutes left, I switched to think about dynamic solution. That was based on the fact that even for naive approach I initialized element with $last = -1$ (left to right) or $last = MAXINT$ (right to left) which means we can incrementally build the answer based on the previosly selected value.\n\nSurprisingly, that\'s one of the tasks where coming up with bottom-up approach is much easier than going with recursive solution first. Unfortunately, I\'ve spent too much time on naive approach and didn\'t make it for the contest, but solved 5 minuters after :|\n\n# Approach\nFor the previously selected value we can select either $nums1[i-1]$ or $nums2[i-1]$, for the current value we also take new value either from $nums1[i]$ or $nums2[i]$. It is good to note that it is possible to select $nums1[i]$ if previous value is $nums2[i-1]$, so we can interleave nums1 and nums2 to form any combinations.\n\nNow, what are possible combinations? \n$nums1[i-1] -> nums1[i]$\n$nums1[i-1] -> nums2[i]$\n\n$nums2[i-1] -> nums1[i]$\n$nums2[i-1] -> nums2[i]$\n\nSo, once we\'ve built the previous sequence, we can add one or the other value and see if that can really increase any of the previous sequences.\n\nIt\'s time to define our function, transition and base state.\n\nLet $dp(current, index)$ be a longest non-decreasing subsequence ending at $index$ if current value is $current$ array value(i.e. $current$ is either 0(nums1) or 1(nums2)).\n\nLet transition be \n$dp[0][i] = dp[x][i - 1] + 1$ if nums1[i] forms non decreasing sequence with previous value\n$dp[1][i] = dp[x][i - 1] + 1$ if nums2[i] forms non decreasing sequence with previous value\nx - can be any of the previous value arrays, so we need to select $MAX$ value among choices.\n\nHowever, if we can\'t really continue any sequence with the new value, we "break" the previous sequence and current sequence is just the single element (similar to base case below).\n\nLet base state be\n$dp[0][0] = 1$ \n$dp[1][0] = 1$\nwe don\'t have any previous values for a first item, so whenever we take the first item, the length is always just 1.\n\n# Complexity\n- Time complexity:\n$$O(n)$$ - just a straightforward iteration over n elements\n\n- Space complexity:\n$$O(n)$$ - dynamic array takes linear space\n\n# Code\n```\nclass Solution {\n    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {\n        int n = nums1.length;\n        \n        int result = 1;\n        \n        // dp[current][index]\n        int[][] dp = new int[2][n];\n\n        // base state\n        dp[0][0] = 1;\n        dp[1][0] = 1;\n\n        for (int i = 1; i < n; ++i) {\n            // transition if we select nums1[i]\n            dp[0][i] = Math.max(\n                nums1[i] >= nums1[i-1] ? dp[0][i-1] + 1 : 1,\n                nums1[i] >= nums2[i-1] ? dp[1][i-1] + 1 : 1\n            ); \n\n            // transition if we select nums2[i]\n            dp[1][i] = Math.max(\n                nums2[i] >= nums1[i-1] ? dp[0][i-1] + 1 : 1,\n                nums2[i] >= nums2[i-1] ? dp[1][i-1] + 1 : 1\n            );\n\n            // keep updating the result on the go\n            // or iterate over DP in the end to find MAX\n            result = Math.max(result, Math.max(dp[0][i], dp[1][i]));\n        }        \n        \n        return result;\n    }\n}\n```
['Dynamic Programming', 'Java']