Medium

题目描述

给定一个整数数组 nums，返回可以从数组中选择的元素的最大和，使得这个和能被三整除。

示例 1：

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

示例 2：

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

示例 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

解题思路

这是一个经典的动态规划问题，核心思想是跟踪不同余数状态下的最大和。

解题思路：

我们需要理解一个数学性质：如果数字的和除以3的余数为0，那么这个和就能被3整除。因此，我们可以维护三个状态：

  • dp[0]：当前和除以3余数为0时的最大和
  • dp[1]：当前和除以3余数为1时的最大和
  • dp[2]：当前和除以3余数为2时的最大和

对于数组中的每个数字 num，我们需要考虑加入这个数字后对各个状态的影响：

  • 如果当前状态余数为 i，加入数字 num 后，新状态的余数为 (i + num) % 3

状态转移过程： 遍历每个数字时，我们需要更新所有可能的状态。为了避免在同一轮更新中使用已经更新过的值，我们使用临时变量保存当前状态。

贪心思路（替代方案）： 另一种思路是使用贪心算法：先计算所有数字的和，然后根据总和除以3的余数，移除最小的几个数字使得剩余和能被3整除。

这里我们采用动态规划解法，因为它更加直观且容易理解。

代码实现

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp(3, 0);
        
        for (int num : nums) {
            vector<int> temp = dp;
            for (int i = 0; i < 3; i++) {
                dp[(temp[i] + num) % 3] = max(dp[(temp[i] + num) % 3], temp[i] + num);
            }
        }
        
        return dp[0];
    }
};

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, 0, 0]
        
        for num in nums:
            temp = dp[:]
            for i in range(3):
                dp[(temp[i] + num) % 3] = max(dp[(temp[i] + num) % 3], temp[i] + num)
        
        return dp[0]

public class Solution {
    public int MaxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        
        foreach (int num in nums) {
            int[] temp = (int[])dp.Clone();
            for (int i = 0; i < 3; i++) {
                dp[(temp[i] + num) % 3] = Math.Max(dp[(temp[i] + num) % 3], temp[i] + num);
            }
        }
        
        return dp[0];
    }
}

var maxSumDivThree = function(nums) {
    let dp = [0, 0, 0];
    
    for (let num of nums) {
        let temp = [...dp];
        for (let i = 0; i < 3; i++) {
            dp[(temp[i] + num) % 3] = Math.max(dp[(temp[i] + num) % 3], temp[i] + num);
        }
    }
    
    return dp[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)遍历数组一次，每次处理3个状态
空间复杂度O(1)只使用固定大小的dp数组和临时数组