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 ```