6912. 构造最长非递减子数组 (opens new window)

1.动态规划

思考过程：

• 贪心。策略是当前位置 i 选出比i-1的最小值，然而在个别用例中需要主动放弃i-1构成的递增序列。❌
• 动规。dp[n][2]，表示以第i个位置的元素作为递增子数组结尾的最大长度。
• 进一步，因为i的状态转移只用到i-1位置的结果，因此直接用两个临时变量保存。空间优化为O(1)
  • len1，len2分别表示当前nums1，nums2数组以第i个元素结尾的递增子数组最大长度
  • 每次index=i更新前，需要保存index=i-1的结果

class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int res = 1,len1 = 1,len2=1;
        for (int i = 1; i < nums1.length; i++) {
            int prelen1 = len1, prelen2 = len2;
            if(nums1[i]>=nums1[i-1]&&nums1[i]>=nums2[i-1]){
                len1 = Math.max(prelen1 + 1, len2 + 1);
            } else if (nums1[i] >= nums1[i - 1]) {
                len1=prelen1+1;
            } else if (nums1[i] >= nums2[i - 1]) {
                res = Math.max(res, len1);
                len1 = prelen2 + 1;
            }else{
                res = Math.max(res, len1);
                len1=1;
            }

            if(nums2[i]>=nums1[i-1]&&nums2[i]>=nums2[i-1]){
                len2 = Math.max(prelen1 + 1, prelen2 + 1);
            } else if (nums2[i] >= nums2[i - 1]) {
                len2=prelen2+1;
            } else if (nums2[i] >= nums1[i - 1]) {
                res = Math.max(res, len2);
                len2 = prelen1 + 1;
            }else{
                res = Math.max(res, len2);
                len2=1;
            }
        }
        res = Math.max(res, len1);
        res = Math.max(res, len2);
        return res;
    }
}