題目

給你一個整數陣列 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

1、動態規劃；時間複雜度O(n)，空間複雜度O(1)

func maxSumDivThree(nums []int) int {	dp := [3]int{}	for i := 0; i < len(nums); i++ {		for _, v := range dp {			value := v + nums[i]			dp[value%3] = max(dp[value%3], value)		}	}	return dp[0]}func max(a, b int) int {	if a > b {		return a	}	return b}

Medium題目，藉助動態規劃和求餘，計算餘數為0的結果