本文涉及知识点

C++动态规划

LeetCode2771. 构造最长非递减子数组

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。
让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将 nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。
你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。
以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。
注意：子数组 是数组中的一个连续非空元素序列。
示例 1：
输入：nums1 = [2,3,1], nums2 = [1,2,1]
输出：2
解释：构造 nums3 的方法之一是：
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]
从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。
可以证明 2 是可达到的最大长度。
示例 2：
输入：nums1 = [1,3,2,1], nums2 = [2,2,3,4]
输出：4
解释：构造 nums3 的方法之一是：
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]
整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。
示例 3：
输入：nums1 = [1,1], nums2 = [2,2]
输出：2
解释：构造 nums3 的方法之一是：
nums3 = [nums1[0], nums1[1]] => [1,1]
整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。
提示：
1 <= nums1.length == nums2.length == n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹

动态规划

动态规划的状态表示

dp1[i] 表示 以nums1[i]结尾的最长子数组。dp2[i]表示 以nums2[i]结尾的最长子数组。 空间复杂度：O(n)。

动态规划的转移方程

如果nums1[i] <= nums2[i+1]，则MaxSelf(dp2[i+1],dp1[i]+1)。其它情况类似。总时间复杂度：O(n)。

动态规划的填报顺序

i =1 To n，先dp1，后dp2。

动态规划初始值

全为1。

动态规划的返回值

max(max(dp1),max(dp2))

代码

核心代码

class Solution {
		public:
			int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
				vector<int>* ptr[] = {&nums1 ,&nums2};
				const int N = nums1.size();
				vector<vector<int>> dp(N,vector<int>(2,1));
				int ans = 1;
				for (int i = 1; i < N; i++) {					
					for (int j = 0; j < 2; j++) {
						for (int k = 0; k < 2; k++) {
							if ((*ptr[j])[i - 1] <= (*ptr[k])[i]) {
								dp[i][k] = max(dp[i][k], dp[i - 1][j] + 1);
							}
						}
					}
					ans = max(ans,dp[i][0]);
					ans = max(ans, dp[i][1]);
				}
				return ans;
			}
		};

单元测试

vector<int> nums1,nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 2,3,1 }, nums2 = { 1,2,1 };
			auto res = Solution().maxNonDecreasingLength(nums1, nums2);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 1,3,2,1 }, nums2 = { 2,2,3,4 };
			auto res = Solution().maxNonDecreasingLength(nums1, nums2);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums1 = { 1,1 }, nums2 = { 2,2 };
			auto res = Solution().maxNonDecreasingLength(nums1, nums2);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums1 = { 5,16,15 }, nums2 = { 12,1,14 };
			auto res = Solution().maxNonDecreasingLength(nums1, nums2);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums1 = { 3,19,13,19 }, nums2 = { 20,18,7,14 };
			auto res = Solution().maxNonDecreasingLength(nums1, nums2);
			AssertEx(2, res);
		}