1. 题目
LeetCode 1262. 可被三整除的最大和
1.1 题意
数组中取数,使得和可以整出3且最大,每个数最多选一次
1.2 分析
看数据量,复杂度可以到O(nlogn)往上
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4
思考一下怎么选数,
先想贪心。看出来这个题的答案是需要选数的组合,贪心不出来。
想动态规划。
对于下标i的情况,模3为0,模3为1,模3为2的最大和值可以通过前一个下标i-1记录的情况 + 第i个数分析出来
具体举例来说就是,
当前数模为1:
模0最大和 = 上一个数的模2最大和 + 当前数
模1最大和 = 上一个数的模0最大和 + 当前数
模2最大和 = 上一个数的模1最大和 + 当前数
但并不是每次都会更新(因为求最大值),所以加上一个取max
模0最大和 = max(上一个数的模2最大和 + 当前数, 模0最大和)
模1最大和 = max(上一个数的模0最大和 + 当前数, 模1最大和)
模2最大和 = max(上一个数的模1最大和 + 当前数, 模2最大和)
再加上一点点空间的优化可以做到只用常量级空间,每次的状态只与上次的状态有关,所以可以只记录上一次的状态(类似滚动数组)
加上亿点点细节:
初始时,模为0,1,2的和最大值都为0
那么在规划中,初始为0的情况有些是不能往下传递的
举个例子
mod0=0, mod1=0, mod2=0
当前数为4,模3为1
此时能使用上述转移方程的只有mod1
必须满足这个边界条件才可以
1.3 我的解法
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
// nlogn
// 记录模3为0,1,2的最大和
int mod0=0, mod1=0, mod2=0;
int n = nums.size();
for(int i=0;i<n;i++){
int num = nums[i];
if(num%3==0){
if(mod1 != 0){
// 为什么要加这个判断
// 因为边界初始化
// 如果mod1压根没有值,就不能有mod1继续往下传
// 这很细节 别问我怎么想到这个的 。。。
mod1 += num;
}
if(mod2 != 0){
mod2 += num;
}
mod0 += num;
}
else if(num%3==1){
int tmp0 = mod0, tmp1 = mod1, tmp2 = mod2;
if(tmp2!=0)
mod0 = max(tmp2 + num, mod0);
mod1 = max(tmp0 + num, mod1);
if(tmp1!=0)
mod2 = max(tmp1 + num, mod2);
}
else if(num%3==2){
int tmp0 = mod0, tmp1 = mod1, tmp2 = mod2;
if(tmp1!=0)
mod0 = max(tmp1 + num, mod0);
if(tmp2!=0)
mod1 = max(tmp2 + num, mod1);
mod2 = max(tmp0 + num, mod2);
}
// cout<<num<<" "<<mod0<<" "<<mod1<<" "<<mod2<<endl;
}
return mod0;
}
};
1.4 学习题解反思
时间复杂度O(n), 空间复杂度O(1)
题解的贪心太强了,把数组分成3堆,依次是模3为0,模3为1,模3为2。
接着由上范围限制,这个模3为1、模3为2的集合中选取数的个数的范围限制真的难想。又是学到了的一天。文章来源:https://www.toymoban.com/news/detail-502148.html
1.5 bug日记
1.5.1 边界状态的转移考虑不全
2. 后记
仅分享自己的想法,有意见和指点非常感谢文章来源地址https://www.toymoban.com/news/detail-502148.html
到了这里,关于力扣日记1262的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!