---
# System prepended metadata

title: 2771. Longest Non-decreasing Subarray From Two Arrays
tags: [Leetcode, Dynamic Programming, Medium]

---

Link: https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays/description/
## 思路
一开始以为用greedy做，但是在这个testcase上会fail 
```nums1=[11,7,7,9]``` ```nums2=[19,19,1,7]```
后来看了[这里](https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays/solutions/3739198/java-c-python-dp/)才知道应该用dp
```dp1``` means the maximum step ending with ```A[i]```.
```dp2``` means the maximum step ending with ```B[i]```.

Then cosider these 4 transitions:
```t11``` for ```A[i-1]``` -> ```A[i]```
```t12``` for ```A[i-1]``` -> ```B[i]```
```t21``` for ```B[i-1]``` -> ```A[i]```
```t22``` for ```B[i-1]``` -> ```B[i]```

We update
```dp1 = max(t11, t12)```
```dp2 = max(t12, t22)```
```res = max(res, dp1, dp2)```
## Code
```python=
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans = dp1 = dp2 = 1
        for i in range(1, len(nums1)):
            r11 = dp1+1 if nums1[i-1]<=nums1[i] else 1
            r12 = dp1+1 if nums1[i-1]<=nums2[i] else 1
            r21 = dp2+1 if nums2[i-1]<=nums1[i] else 1
            r22 = dp2+1 if nums2[i-1]<=nums2[i] else 1
            dp1 = max(r11, r21)
            dp2 = max(r12, r22)
            ans = max(ans, dp1, dp2)
        return ans
```
greedy的错误做法
```python=
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans, start, last = 1, 0, -math.inf
        for i in range(len(nums1)):
            n1, n2 = nums1[i], nums2[i]
            if last<=max(n1, n2):
                if last<=min(n1, n2): last = min(n1, n2)
                else: last = max(n1, n2)
            else:
                ans = max(ans, i-start)
                start = i
                last = min(n1, n2)
        ans = max(ans, len(nums1)-start)
        return ans
```