2026-04-28：能被 3 整除的三元组最大和。用go语言，在数组 nums 中挑选出恰好三个数，使得这三个数的总和可以被 3 整除。 要求计算所有

2026-04-28：能被 3 整除的三元组最大和。用go语言，在数组 nums 中挑选出恰好三个数，使得这三个数的总和可以被 3 整除。

要求计算所有满足条件的三元组里，它们的三个数之和所能达到的最大值；如果完全找不到满足条件的三元组，则结果为 0。

3 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入: nums = [4,2,3,1]。

输出: 9。

解释:

总和能被 3 整除的有效三元组为：

(4, 2, 3)，和为 4 + 2 + 3 = 9。

(2, 3, 1)，和为 2 + 3 + 1 = 6。

因此，答案是 9。

题目来自力扣3779。

解题过程详细解析 一、核心定义与初始化准备 1. 关键常量定义

•K=3：我们必须恰好选3个数字，这是固定要求；

•MOD=3：判断和能否被3整除，只需要看总和对3取余的结果（余数只能是0、1、2）。

2. 动态规划数组定义

创建二维数组f，格式：f[选了i个数][余数为r] = 最大和

• 第一维：0~3，代表当前选中的数字个数（0个、1个、2个、3个）；

• 第二维：0~2，代表当前数字总和对3取余的结果；

• 数组值：存储对应状态下的最大总和。

3. 数组初始化

• 所有位置默认赋值为负无穷（表示初始状态不可达，没有有效数字）；

• 唯一初始有效状态：f[0][0] = 0（选0个数，总和为0，余数0，和为0）。

二、核心遍历逻辑（逐个处理数组中的数字）

遍历数组里的每一个数字x，从后往前更新动态规划数组（避免重复使用同一个数字），核心规则：
对于当前已选j个数字、余数为r的状态，加入数字x后，会变成：选j+1个数字、余数为(r+x)%3，总和变为 原总和 + x。
我们只保留每个状态下的最大总和。

分步处理示例（输入数组：[4,2,3,1]）

我们一步步看每个数字处理后，状态的变化：

1.处理第一个数字 4

• 4对3取余=1；

• 从选0个、余数0的状态，更新为：选1个、余数1，和为4；

• 此时有效状态：选1个余数1=4。

2.处理第二个数字 2

• 2对3取余=2；

• 基于选0个的状态：新增 选1个余数2=2；

• 基于选1个余数1的状态：新增 选2个余数0=4+2=6；

• 此时有效状态：选1个(1=4、2=2)，选2个(0=6)。

3.处理第三个数字 3

• 3对3取余=0；

• 基于选0个：新增 选1个余数0=3；

• 基于选1个：更新选2个的最大和（余数1=4+3=7、余数2=2+3=5）；

• 基于选2个余数0：更新选3个余数0=6+3=9（这就是最终答案）；

• 此时已经得到：恰好选3个数、余数0、和为9。

4.处理第四个数字 1

• 1对3取余=1；

• 继续更新所有状态，会得到另一个三元组和为6；

• 对比后，最大和依旧是9。

三、最终结果计算

遍历结束后，我们只需要看一个目标状态：
f[3][0]：恰好选3个数字，总和余数为0（能被3整除）的最大和。

• 如果这个值大于0，就返回它；

• 如果这个值无效（负无穷），说明没有符合条件的三元组，返回0。

示例中f[3][0]=9，所以最终输出9。

四、时间复杂度 & 额外空间复杂度 1. 时间复杂度

• 设数组长度为n（最大10万）；

• 动态规划的两层固定循环：选数字个数（3次）+ 余数（3次）= 固定9次操作；

• 总操作次数 =n × 9，是线性复杂度；

•时间复杂度：O(n)。

2. 额外空间复杂度

• 动态规划数组是固定大小：4行 × 3列 = 12个元素；

• 空间大小不随数组长度变化，是常数级空间；

•额外空间复杂度：O(1)。

总结

1. 解题核心：用动态规划记录「选几个数+总和余数」的最大和，精准匹配「恰好3个数、能被3整除」的要求；

2. 处理逻辑：逐个遍历数字，更新所有可能的状态，只保留最大和；

3. 效率：时间O(n)（处理10万数据极快），空间O(1)（占用内存极小），完全满足题目数据规模要求。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func maximumSum(nums []int)int {
    const K = 3
    const MOD = 3
    f := [K + 1][MOD]int{}
    for i := range f {
        for j := range f[i] {
            f[i][j] = math.MinInt
        }
    }
    f[0][0] = 0
    for _, x := range nums {
        for j := K - 1; j >= 0; j-- {
            for r := range MOD {
                f[j+1][(r+x)%MOD] = max(f[j+1][(r+x)%MOD], f[j][r]+x)
            }
        }
    }
    return max(f[K][0], 0)
}

 func main() {
    nums := []int{4, 2, 3, 1}
    result := maximumSum(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import math

 def maximum_sum(nums):
    K = 3
    MOD = 3
    # 初始化 dp 表，dp[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和
    dp = [[-math.inf] * MOD for _ in range(K + 1)]
    dp[0][0] = 0

     for x in nums:
        # 倒序更新 j，确保每个数最多选一次（0/1 背包）
        for j in range(K - 1, -1, -1):
            for r in range(MOD):
                # 避免在更新过程中使用本轮已更新的值，倒序 j 已保证
                new_r = (r + x) % MOD
                if dp[j][r] != -math.inf:
                    dp[j + 1][new_r] = max(dp[j + 1][new_r], dp[j][r] + x)

     # 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0
    return max(dp[K][0], 0)

 if __name__ == "__main__":
    nums = [4, 2, 3, 1]
    result = maximum_sum(nums)
    print(result)  

C++完整代码如下：

  

  

   


 using namespace std;

 int maximumSum(vector& nums) {
    constint K = 3;
    constint MOD = 3;

     // 初始化 dp 表，f[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和
    vector 
 
 int 
 >> f(K +  
 1 
 , vector< 
 int 
 >(MOD, INT_MIN)); 
 
 
     f[ 
 0 
 ][ 
 0 
 ] =  
 0 
 ; 
 
 
 
 
      
 for 
  ( 
 int 
  x : nums) { 
 
 
          
 // 倒序更新 j，确保每个数只使用一次 
 
 
          
 for 
  ( 
 int 
  j = K -  
 1 
 ; j >=  
 0 
 ; j--) { 
 
 
              
 for 
  ( 
 int 
  r =  
 0 
 ; r < MOD; r++) { 
 
 
                  
 if 
  (f[j][r] != INT_MIN) { 
 
 
                      
 int 
  new_r = (r + x) % MOD; 
 
 
                     f[j +  
 1 
 ][new_r] = max(f[j +  
 1 
 ][new_r], f[j][r] + x); 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0 
 
 
      
 return 
  max(f[K][ 
 0 
 ],  
 0 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 4 
 ,  
 2 
 ,  
 3 
 ,  
 1 
 }; 
 
 
      
 int 
  result = maximumSum(nums); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。