北京
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）。
創建二維數組f，格式：f[選了i個數][余數為r] = 最大和
? 第一維：
0~3，代表當前選中的數字個數（0個、1個、2個、3個）；? 第二維：
0~2，代表當前數字總和對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)。
? 動態規劃數組是固定大小：
4行 × 3列 = 12個元素；? 空間大小不隨數組長度變化，是常數級空間；
?額外空間復雜度：O(1)。
1. 解題核心：用動態規劃記錄「選幾個數+總和余數」的最大和，精準匹配「恰好3個數、能被3整除」的要求；
2. 處理邏輯：逐個遍歷數字，更新所有可能的狀態，只保留最大和；
3. 效率：時間O(n)（處理10萬數據極快），空間O(1)（占用內存極小），完全滿足題目數據規模要求。
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助力您的未來發展。
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
