Solution Explanation for LeetCode 1262: Greatest Sum Divisible by Three

This problem asks to find the maximum sum of a subset of numbers from an input array nums such that the sum is divisible by 3. We can solve this efficiently using dynamic programming or a greedy approach. Both approaches are explained below.

Approach 1: Dynamic Programming

This approach uses a 2D DP array f[i][j] where i represents the index of the current number in nums, and j represents the remainder when the current sum is divided by 3 (0, 1, or 2). f[i][j] stores the maximum sum achievable with the first i numbers such that the remainder is j.

State Transition:

For each number x in nums, we have two choices:

1. Include x: The new remainder is (j - x % 3 + 3) % 3. The new sum is f[i-1][(j - x % 3 + 3) % 3] + x.
2. Exclude x: The remainder stays the same. The new sum is f[i-1][j].

We take the maximum of these two choices for each i and j. The final answer is f[n][0], where n is the length of nums.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of nums. We iterate through the array once. The DP table is of size 3*n. however, we optimize it to O(1) space.
• Space Complexity: O(1). We can optimize the space to O(1) using a rolling array or just three variables to store the current row.

Code (Python):

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, -float('inf'), -float('inf')] # Initialize DP array. [sum%3 == 0, sum%3 == 1, sum%3 ==2]
        for num in nums:
            new_dp = dp[:] # Create a copy to avoid overwriting values
            for i in range(3):
                new_dp[i] = max(dp[i], dp[(i - num % 3 + 3) % 3] + num) #DP transition
            dp = new_dp #update dp
        return dp[0]

Approach 2: Greedy Approach (Optimization)

This is a more optimized greedy approach. The idea is to first calculate the total sum of all numbers. If the total sum is divisible by 3, we're done. Otherwise, we need to remove some numbers to make the sum divisible by 3. The greedy strategy involves finding the smallest numbers with remainder 1 and 2 modulo 3, to remove to adjust the remainder to 0.

Algorithm:

1. Calculate the total sum total_sum.
2. If total_sum % 3 == 0, return total_sum.
3. If total_sum % 3 == 1, find the smallest two numbers with remainder 1 modulo 3 or one number with remainder 1 and remove them.
4. If total_sum % 3 == 2, find the smallest two numbers with remainder 2 modulo 3 or one number with remainder 2 and remove it.

Time and Space Complexity:

• Time Complexity: O(n log n) due to sorting if we need to find the smallest numbers. If we don't sort, it is O(n)
• Space Complexity: O(1)

Code (Python):

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        if total_sum % 3 == 0:
            return total_sum
 
        remainder1 = []
        remainder2 = []
        for num in nums:
            if num % 3 == 1:
                remainder1.append(num)
            elif num % 3 == 2:
                remainder2.append(num)
 
        if total_sum % 3 == 1:
            if len(remainder1) >= 2:
                remainder1.sort()
                total_sum -= (remainder1[0] + remainder1[1])
            elif remainder1:
                total_sum -= remainder1[0]
        elif total_sum % 3 == 2:
            if len(remainder2) >=2:
                remainder2.sort()
                total_sum -= (remainder2[0]+remainder2[1])
            elif remainder2:
                total_sum -= remainder2[0]
        return max(0, total_sum) #return 0 if no solution is found
 
 

Both approaches solve the problem correctly. The dynamic programming approach is generally easier to understand and implement, while the optimized greedy approach can be slightly faster in some cases. The choice depends on your preference and the specific constraints of your application.