1262-可被三整除的最大和

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

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

示例 1：

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

method

回溯不出意外超时，改用动态规划

mod[k]表示累加nums[0-i]模以3余数为k的最大值

int maxSumDivThree(vector<int>& nums) {
    int mod[3] = {0};
    for (int i = 0; i < nums.size(); i++) {
        int a = mod[0] + nums[i];
        int b = mod[1] + nums[i];
        int c = mod[2] + nums[i];
        mod[a % 3] = max(mod[a % 3], a);
        mod[b % 3] = max(mod[b % 3], b);
        mod[c % 3] = max(mod[c % 3], c);
    }
    return mod[0];
}