主題
題目連結(jié)：
題目意譯：
你被給定兩個索引值從 0 開始數(shù)的整數(shù)陣列 nums1 和 nums2，兩者長度皆為 n。
定義另一個索引值從 0 開始數(shù)的整數(shù)陣列 nums3，長度一樣為 n。對於位於範(fàn)圍 [0, n - 1] 中的每一個索引值 i，你可以選擇將 nums3[i] 之值設(shè)為 nums1[i] 或是 nums2[i]。
你的任務(wù)是藉由按最佳策略選擇填入的數(shù)字來最大化 nums3 中最長非遞減子陣列之長度。
回傳一個整數(shù)代表 nums3 中最長非遞減子陣列之長度。
注： 一個子陣列為一個陣列中一段連續(xù)非空元素序列。
限制：
1 ≦ nums1.length == nums2.length == n ≦ 10 ^ 5
1 ≦ nums1[i], nums2[i] ≦ 10 ^ 9
範(fàn)例測資：
範(fàn)例 1：
輸入： nums1 = [2,3,1], nums2 = [1,2,1]
輸出： 2
解釋： 建構(gòu) nums3 的其中一個方式為：
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]。
以索引值 0 開頭並以索引值 1 結(jié)尾的子陣列 [2,2]，會形成一個長度為 2 的非遞減子陣列。
可以證明最長可以達成的長度為 2。
範(fàn)例 2：
輸入： nums1 = [1,3,2,1], nums2 = [2,2,3,4]
輸出： 4
解釋： 建構(gòu) nums3 的其中一個方式為：
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]。
整個陣列會形成一個長度為 4 的非遞減子陣列，因此其為最大可達成的長度。
範(fàn)例 3：
輸入： nums1 = [1,1], nums2 = [2,2]
輸出： 2
解釋： 建構(gòu) nums3 的其中一個方式為：
nums3 = [nums1[0], nums1[1]] => [1,1]。
整個陣列會形成一個長度為 4 的非遞減子陣列，因此其為最大可達成的長度。
解題思維：
某方面來說很像這題。
當(dāng)然，動態(tài)規(guī)劃（Dynamic Programming）用的陣列之定義不同。在本題中，D[i][j] 代表著在以 nums1[i] 作為結(jié)尾（j = 0）或是以 nums2[i] 作為結(jié)尾（j = 1）的最長非遞減子陣列之長度。
而遞迴式為：
D[0][0] = D[0][1] = 1；
（上式為停止條件）
如果 nums1[i - 1] > nums1[i] 且 nums2[i - 1] > nums1[i]，D[i][0] = 1；
如果 nums1[i - 1] ≦ nums1[i] 且 nums2[i - 1] > nums1[i]，D[i][0] = D[i - 1][0] + 1；
如果 nums1[i - 1] > nums1[i] 且 nums2[i - 1] ≦ nums1[i]，D[i][0] = D[i - 1][1] + 1；
如果 nums1[i - 1] ≦ nums1[i] 且 nums2[i - 1] ≦ nums1[i]，D[i][0] = max(D[i - 1][0], D[i - 1][1]) + 1；
如果 nums1[i - 1] > nums2[i] 且 nums2[i - 1] > nums2[i]，D[i][1] = 1；
如果 nums1[i - 1] ≦ nums2[i] 且 nums2[i - 1] > nums2[i]，D[i][1] = D[i - 1][0] + 1；
如果 nums1[i - 1] > nums2[i] 且 nums2[i - 1] ≦ nums2[i]，D[i][1] = D[i - 1][1] + 1；
如果 nums1[i - 1] ≦ nums2[i] 且 nums2[i - 1] ≦ nums2[i]，D[i][1] = max(D[i - 1][0], D[i - 1][1]) + 1；
而所求即為過程中 D[i][0] 、 D[i][1] 之最大值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
