LeetCode-1262. Greatest Sum Divisible by Three

LeetCode-1262. Greatest Sum Divisible by Three

Given an array ​​nums​​ of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]Output: 18Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]Output: 0Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]Output: 12Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

​​1 <= nums.length <= 4 * 10^4​​​​1 <= nums[i] <= 10^4​​

​​题解：​​

​​之前只想到O(n^2)解法，看讨论区解法：​​

​​使用两个数字维护目前为止数组中组成的余数为1和2的数字最小组成，判断最终结果如果正好整除、余数为1（减去数组中最小组成余数1的数字大小）、余数为2（减去数组中最小组成余数2的数字大小）。​​

​​该算法可以扩展到整除任意数字的最大值。​​

class Solution {public: int maxSumDivThree(vector& nums) { int n = nums.size(); if (n == 0) { return 0; } long dp = 0, dp1 = INT_MAX, dp2 = INT_MAX, sum = 0; for (int i = 0; i < n; i++) { if (nums[i] % 3 == 1) { dp2 = min(dp2, dp1 + long(nums[i])); dp1 = min(dp1, long(nums[i])); } if (nums[i] % 3 == 2) { dp1 = min(dp1, dp2 + long(nums[i])); dp2 = min(dp2, long(nums[i])); } sum += nums[i]; } if (sum % 3 == 0) { return sum; } if (sum % 3 == 1) { return sum - dp1; } return sum - dp2; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。