Leetcode Problem 2771. Longest Non-decreasing Subarray From Two Arrays

2771. Longest Non-decreasing Subarray From Two Arrays

Leetcode Solutions

Dynamic Programming with Two States

  1. Initialize ans, s0, and s1 to 1, representing the length of the longest non-decreasing subarray found so far, and the lengths of the subarrays ending at the previous index for nums1 and nums2, respectively.
  2. Iterate over the arrays from index 1 to n - 1.
  3. For each index i, update s0 and s1 as follows:
    • s0 becomes the maximum of s0 (if nums1[i-1] <= nums1[i]) and s1 (if nums2[i-1] <= nums1[i]) plus 1.
    • s1 becomes the maximum of s0 (if nums1[i-1] <= nums2[i]) and s1 (if nums2[i-1] <= nums2[i]) plus 1.
  4. Update ans with the maximum of ans, s0, and s1.
  5. Return ans as the result.
UML Thumbnail

Brute Force with Optimization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...