1262. 可被三整除的最大和

题目描述

给你一个整数数组 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func max(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val > res {
            res = val
        }
    }
    return res
}

func maxSumDivThree(nums []int) int {
    n := len(nums)
    dp := make([][3]int, n)
    dp[0][nums[0]%3] = nums[0]
    for i := 1; i < n; i++ {
        cur := nums[i] % 3
        if cur == 0 {
            dp[i][0] = dp[i-1][0] + nums[i]
            dp[i][1] = dp[i-1][1] + nums[i]
            dp[i][2] = dp[i-1][2] + nums[i]
        } else if cur == 1 {
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]+nums[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+nums[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]+nums[i])
        } else if cur == 2 {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][2]+nums[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][0]+nums[i])
        }
    }
    return dp[n-1][0]
}

错误原因：

当 nums[0] == 1 时，初始化 dp[0][2] = 0 ，但是此时 dp[0][2] % 3 == 2 不成立。

正确代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


func max(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val > res {
            res = val
        }
    }
    return res
}

func maxSumDivThree(nums []int) int {
    n := len(nums)
    dp := make([][3]int, n)
    dp[0][nums[0]%3] = nums[0]
    for i := 1; i < n; i++ {
        cur := nums[i] % 3
        if cur == 0 {
            if dp[i-1][0] == 0 {
                dp[i][0] = nums[i]
            } else {
                dp[i][0] = dp[i-1][0] + nums[i]
            }

            if dp[i-1][1] != 0 {
                dp[i][1] = dp[i-1][1] + nums[i]
            }
            if dp[i-1][2] != 0 {
                dp[i][2] = dp[i-1][2] + nums[i]
            }
        } else if cur == 1 {
            if dp[i-1][0] != 0 {
                dp[i][1] = max(dp[i-1][1], dp[i-1][0]+nums[i])
            } else {
                dp[i][1] = max(dp[i-1][1], nums[i])
            }

            if dp[i-1][1] != 0 {
                dp[i][2] = max(dp[i-1][1]+nums[i], dp[i-1][2])
            } else {
                dp[i][2] = dp[i-1][2]
            }

            if dp[i-1][2] != 0 {
                dp[i][0] = max(dp[i-1][0], dp[i-1][2] + nums[i])
            } else {
                dp[i][0] = dp[i-1][0]
            }
        } else if cur == 2 {
            if dp[i-1][0] != 0 {
                dp[i][2] = max(dp[i-1][2], dp[i-1][0] + nums[i])
            } else {
                dp[i][2] = max(dp[i-1][2], nums[i])
            }

            if dp[i-1][1] != 0 {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i])
            } else {
                dp[i][0] = dp[i-1][0]
            }

            if dp[i-1][2] != 0 {
                dp[i][1] = max(dp[i-1][1], dp[i-1][2] + nums[i])
            } else {
                dp[i][1] = dp[i-1][1]
            }
        }
    }
    return dp[n-1][0]
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxSumDivThree(nums []int) int {
    f := []int{0, -0x3f3f3f3f, -0x3f3f3f3f}
    for _, num := range nums {
        g := make([]int, 3)
        for i := 0; i < 3; i++ {
            g[(i + num) % 3] = max(f[(i + num) % 3], f[i] + num)
        }
        f = g
    }
    return f[0]
}

解法二：贪心 + 正向思维

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


func max(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val > res {
            res = val
        }
    }
    return res
}

func maxSumDivThree(nums []int) int {
    var arr [3][]int
    for _, num := range nums {
        remainder := num % 3
        arr[remainder] = append(arr[remainder], num)
    }
    sort.Slice(arr[1], func(i, j int) bool {
        return arr[1][i] > arr[1][j]
    })
    sort.Slice(arr[2], func(i, j int) bool {
        return arr[2][i] > arr[2][j]
    })
    fmt.Println(arr[1], arr[2])
    lb, lc := len(arr[1]), len(arr[2])
    var ans int
    for cntb := lb - 2; cntb <= lb; cntb++ {
        if cntb >= 0 {
            for cntc := lc - 2; cntc <= lc; cntc++ {
                if cntc >= 0 && (cntb-cntc)%3 == 0 {
                    sum := 0
                    for i := 0; i < cntb; i++ {
                        sum += arr[1][i]
                    }
                    for i := 0; i < cntc; i++ {
                        sum += arr[2][i]
                    }
                    ans = max(ans, sum)
                }
            }
        }
    }
    for i := 0; i < len(arr[0]); i++ {
        ans += arr[0][i]
    }
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func accumulate(v []int) int {
    ans := 0
    for _, x := range v {
        ans += x
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxSumDivThree(nums []int) int {
    // 使用 v[0], v[1], v[2] 分别表示 a, b, c
    v := make([][]int, 3)
    for _, num := range nums {
        v[num % 3] = append(v[num % 3], num)
    }
    sort.Slice(v[1], func(i, j int) bool {
        return v[1][i] > v[1][j]
    })
    sort.Slice(v[2], func(i, j int) bool {
        return v[2][i] > v[2][j]
    })
    ans, lb, lc := 0, len(v[1]), len(v[2])
    for cntb := max(lb - 2, 0); cntb <= lb; cntb++ {
        for cntc := max(lc - 2, 0); cntc <= lc; cntc++ {
            if (cntb - cntc) % 3 == 0 {
                ans = max(ans, accumulate(v[1][:cntb]) + accumulate(v[2][:cntc]))
            }
        }
    }
    return ans + accumulate(v[0])
}

解法三：贪心 + 逆向思维

在方法一中，我们使用的是「正向思维」，即枚举 b 和 c 中分别选出了多少个数。我们同样也可以使用「逆向思维」，枚举 b 和 c 中分别丢弃了多少个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


func min(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val < res {
            res = val
        }
    }
    return res
}

func maxSumDivThree(nums []int) int {
    var arr [3][]int
    sum := 0
    for i := 0; i < len(nums); i++ {
        remainder := nums[i] % 3
        arr[remainder] = append(arr[remainder], nums[i])
        sum += nums[i]
    }
    sort.Slice(arr[1], func(i, j int) bool {
        return arr[1][i] > arr[1][j]
    })
    sort.Slice(arr[2], func(i, j int) bool {
        return arr[2][i] > arr[2][j]
    })

    remove := math.MaxInt32
    if sum%3 == 0 {
        return sum
    } else if sum%3 == 1 {
        if len(arr[1]) >= 1 {
            remove = min(remove, arr[1][len(arr[1])-1])
        }
        if len(arr[2]) >= 2 {
            remove = min(remove, arr[2][len(arr[2])-1]+arr[2][len(arr[2])-2])
        }
    } else {
        // sum % 3 == 2
        if len(arr[1]) >= 2 {
            remove = min(remove, arr[1][len(arr[1])-1]+arr[1][len(arr[1])-2])
        }
        if len(arr[2]) >= 1 {
            remove = min(remove, arr[2][len(arr[2])-1])
        }
    }
    return sum - remove
}