Greatest Sum Divisible by Three

Spent a weekend on this LeetCode problem and it was surprisingly satisfying. At first glance it seems simple - just find the max sum divisible by 3 - but the solution reveals some nice algorithmic thinking.

My initial approach

I started with the greedy idea: sum everything, then fix the remainder. If sum % 3 == 1, either remove the smallest number with remainder 1, or two numbers with remainder 2. Simple and intuitive.

func maxSumDivisibleBy3(nums []int) int {
    sum := 0
    var rem1, rem2 []int
    
    for _, num := range nums {
        sum += num
        switch num % 3 {
        case 1: rem1 = append(rem1, num)
        case 2: rem2 = append(rem2, num)
        }
    }
    
    if sum % 3 == 0 { return sum }
    if sum % 3 == 1 {
        if len(rem1) > 0 {
            return sum - min(rem1...)
        }
        if len(rem2) >= 2 {
            sort.Ints(rem2)
            return sum - rem2[0] - rem2[1]
        }
    }
    // similar logic for remainder 2
    return 0
}

Then I discovered DP

What's cool is there's a DP approach that tracks the best sum for each remainder state. It's more elegant but maybe overkill for this problem.

func maxSumDivisibleBy3DP(nums []int) int {
    dp := [3]int{0, math.MinInt32, math.MinInt32}
    for _, num := range nums {
        cur := dp
        for r := 0; r < 3; r++ {
            newR := (r + num % 3) % 3
            dp[newR] = max(dp[newR], cur[r] + num)
        }
    }
    return max(0, dp[0])
}

What I learned

Sometimes the greedy approach is perfectly fine and more readable. The DP solution is clever but adds complexity without much benefit here. Still, it's good to know both patterns.

Fun problem - makes you think about remainders in a different way!