本文涉及知识点
数论 区间合并
LeetCode3041. 修改数组后最大化数组中的连续元素数目
给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
示例 1：
输入：nums = [2,1,5,1,1]
输出：3
解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。
我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。
最多可以得到 3 个连续元素。
示例 2：
输入：nums = [1,4,7,10]
输出：1
解释：我们可以选择的最多元素数目是 1 。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 106
数论
先排序。
合并方式一：如果[left,r]中的数至少出现1次，则可以通过将所有数+1，从[left,r]转化成[left+1,r+1]。
合并方式二：如果[left,r]中的数至少出现1次，且至少一个数x出现两次。则可以将[left,r]转化成[left,r+1]。x→ \rightarrow→x+1,x+1→ \rightarrow→x+2 ⋯ \cdots⋯ r → \rightarrow→ r+1。 如： {1,1,2,3} → \rightarrow→ {1,2,3,4}
如果 [l1,r1] 和[l2,r2] 是合法区间，r1+2= l2
方式一合并后，变成[l1+1,r2] ，由于缺少l1,合并后无法合并更小的区间。
方式二合并后，变成[l1,r2]，可以继续合并更小的区间。
合并后的重复数字以[l2,r2]为准，[l1,r1]无论有多少个数字多不能变成r1+2，所以不会影响新区间。
我们枚举方式二的开始，如果 [l1,r1] 和[l2,r2] 能通过方式二合并，则无需枚举[l2,r2]。
代码
核心代码
template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } #define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) class Solution { public: int maxSelectedElements(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<tuple<int, int, bool>> vLRTow; int left = 0; bool bRepeat = false; for (int i = 1; i < nums.size(); i++) { if (nums[i] == nums[i - 1]) { bRepeat = true; } else if (nums[i] != nums[i - 1] + 1) { vLRTow.emplace_back(nums[left], nums[i - 1], bRepeat); left = i; bRepeat = false; } } vLRTow.emplace_back(nums[left], nums.back(), bRepeat); std::unordered_map<int, int> mEndToLen; for (const auto& [left, r, tmp] : vLRTow) { mEndToLen[r] = r - left + 1; } vector<tuple<int, int, bool>> vLRTow2; for (int i = 0; i < vLRTow.size(); ) { vLRTow2.emplace_back(vLRTow[i]); i++; for ( ; i < vLRTow.size(); i ++) { if (get<2>(vLRTow2.back()) && (get<1>(vLRTow2.back()) + 2 == get<0>(vLRTow[i]))) { get<2>(vLRTow2.back()) = get<2>(vLRTow[i]); get<1>(vLRTow2.back()) = get<1>(vLRTow[i]); } else { break; } } } int iRet = 0; for (int i = 0 ; i < vLRTow2.size();i++) { const auto& [left, r, bReapt] = vLRTow2[i]; int pre = mEndToLen.count(left-2 )? mEndToLen[left-2] :0; MaxSelf(&iRet, pre + r - left + 1 + bReapt); } return iRet; } };
测试用例
int main() { vector<int> nums; { Solution sln; nums = { 16,1,6,14,5,10,16,3,3,7,12,18,6,11,10,10,9,16 }; auto res = sln.maxSelectedElements(nums); Assert(13, res); } { Solution sln; nums = { 9, 8, 8, 5, 15, 9, 12, 5, 1, 3, 7, 18, 10 }; auto res = sln.maxSelectedElements(nums); Assert(9, res); } { Solution sln; nums = { 8,13,18,10,16,19,11,17,15,18,9,12,15,8,9,14,7 }; auto res = sln.maxSelectedElements(nums); Assert(14, res); } { Solution sln; nums = { 12, 11, 8, 7, 2, 10, 18, 12 }; auto res = sln.maxSelectedElements(nums); Assert(6, res); } { Solution sln; nums = { 8,10,6,12,9,12,2,3,13,19,11,18,10,16 }; auto res = sln.maxSelectedElements(nums); Assert(8, res); } { Solution sln; nums = { 2,1,4,1,1 }; auto res = sln.maxSelectedElements(nums); Assert(4, res); } { Solution sln; nums = { 2,1,5,1,1 }; auto res = sln.maxSelectedElements(nums); Assert(3, res); } }
优化代码：简洁
template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } #define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) class Solution { public: int maxSelectedElements(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<tuple<int, int, bool>> vLRTow; int left = 0; bool bRepeat = false; for (int i = 1; i < nums.size(); i++) { if (nums[i] == nums[i - 1]) { bRepeat = true; } else if (nums[i] != nums[i - 1] + 1) { vLRTow.emplace_back(nums[left], nums[i - 1], bRepeat); left = i; bRepeat = false; } } vLRTow.emplace_back(nums[left], nums.back(), bRepeat); int iRet = 0; for (int i = 0; i < vLRTow.size(); ) { int j = i + 1; int right = get<1>(vLRTow[i]) + get<2>(vLRTow[i]); for (; j < vLRTow.size(); j++) { if (get<2>(vLRTow[j-1]) && (get<1>(vLRTow[j - 1]) + 2 == get<0>(vLRTow[j]))) { right = get<1>(vLRTow[j]) + get<2>(vLRTow[j]); } else { break; } } int pre = ((i > 0) && (get<1>(vLRTow[i - 1]) + 2 == get<0>(vLRTow[i]))) ? (get<1>(vLRTow[i - 1]) - get<0>(vLRTow[i - 1]) + 1) : 0; MaxSelf(&iRet, right - get<0>(vLRTow[i])+1 + pre ); i = j; } return iRet; } };
动态规划
动态规划的状态
dp[x]表示以x结尾的最长连续数量。
动态规划的初始值
无，或者或全部为0。
动态规划的状态方程
动态规划的填表顺序
x从小到大。先处理x+1，再处理x。否则{1}的结果是dp[1]=1,dp[2]=2。
代码
template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } class Solution { public: int maxSelectedElements(vector<int>& nums) { sort(nums.begin(), nums.end()); unordered_map<int, int> dp; for (const auto& n : nums) { MaxSelf(&dp[n + 1], dp[n] + 1); MaxSelf(&dp[n ], dp[n - 1] + 1); } int iRet = 0; for (const auto& [tmp, len] : dp) { MaxSelf(&iRet, len); } return iRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
