可被三整除的最大和【LC1262】
给你一个整数数组
nums，请你找出并返回能被三整除的元素最大和。
- 思路
题目要求求出能被3整除的最大和，那么我们可以记录每种余数对应的最大和【贪心，相同余数的情况下取最大值】，那么答案即为val[0]。枚举每一个数，将其与目前的最大和相加得到三个可能的答案，然后存入数组中记录最大值 - 实现
class Solution { public int maxSumDivThree(int[] nums) { // 哈希表 int[] val = new int[3];// 记录余数对应的最大和->那么答案即为val[0] for (int num : nums){ int a = val[0] + num; int b = val[1] + num; int c = val[2] + num; val[a % 3] = Math.max(a, val[a % 3]); val[b % 3] = Math.max(b, val[b % 3]); val[c % 3] = Math.max(c, val[c % 3]); } return val[0]; } }
class Solution { public int maxSumDivThree(int[] nums) { int n = nums.length; var memo = new int[n][3]; for (int i = 0; i < n; i++) Arrays.fill(memo[i], -1); // -1 表示没有计算过 return dfs(memo, nums, n - 1, 0); } private int dfs(int[][] memo, int[] nums, int i, int j) { if (i < 0) return j == 0 ? 0 : Integer.MIN_VALUE; if (memo[i][j] != -1) return memo[i][j]; // 之前计算过 return memo[i][j] = Math.max(dfs(memo, nums, i - 1, j), dfs(memo, nums, i - 1, (j + nums[i]) % 3) + nums[i]); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/solutions/2313700/liang-chong-suan-fa-tan-xin-dong-tai-gui-tsll/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
递推
扩展一维找到边界
class Solution { public int maxSumDivThree(int[] nums) { int n = nums.length; var f = new int[n + 1][3]; f[0][1] = f[0][2] = Integer.MIN_VALUE; for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) f[i + 1][j] = Math.max(f[i][j], f[i][(j + nums[i]) % 3] + nums[i]); return f[n][0]; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/solutions/2313700/liang-chong-suan-fa-tan-xin-dong-tai-gui-tsll/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
