LeetCode 1262: 可被三整除的最大和

[guodongxiaren]

https://leetcode-cn.com/problems/greatest-sum-divisible-by-three

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

 

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：

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

[guodongxiaren]

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int dp[3] = {0};
        int tmp[3] = {0};

        for (int n: nums) {
            memcpy(tmp, dp, sizeof(int)*3);

            for (int i = 0; i < 3; ++i) {
                if ((n + dp[i]) % 3 == 0) {
                    tmp[0] = max(n+dp[i], tmp[0]);
                } else if ((n + dp[i]) % 3 == 1) {
                    tmp[1] = max(n+dp[i], tmp[1]);
                } else {
                    tmp[2] = max(n+dp[i], tmp[2]);
                }
            }

            memcpy(dp, tmp, sizeof(int)*3);
        }
        return dp[0];
    }
};

[guodongxiaren]

改进：减少一次memcpy！

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int dp[3] = {0};
        int tmp[3] = {0};

        for (int n: nums) {
            memcpy(tmp, dp, sizeof(int)*3);

            for (int i = 0; i < 3; ++i) {
                if ((n + tmp[i]) % 3 == 0) {
                    dp[0] = max(n+tmp[i], dp[0]);
                } else if ((n + tmp[i]) % 3 == 1) {
                    dp[1] = max(n+tmp[i], dp[1]);
                } else {
                    dp[2] = max(n+tmp[i], dp[2]);
                }
            }
        }
        return dp[0];
    }
};