We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Greatest Sum Divisible by Three

Number: 1388

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given an integer array nums, return the maximum possible sum of elements of the array such that the sum is divisible by three. If no combination makes the sum divisible by three, return 0.

Key Insights

  • The problem focuses on maximizing a sum that is divisible by three.
  • Instead of trying all subsets which is inefficient, we can use dynamic programming to store the best possible sums for each remainder modulo 3.
  • The idea is to maintain a state for each remainder (0, 1, 2).
  • When processing each number, update the potential maximum sum for each remainder by considering the number added to previous state values.
  • Use a temporary copy for state update to avoid interfering with the ongoing iteration.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the nums array. Space Complexity: O(1), since we only maintain a fixed-size array (size 3) for the dynamic programming state.

Solution

We use a dynamic programming approach where we maintain an array, dp, of size 3. Each index i in dp represents the maximum sum we can achieve that has a remainder i when divided by three. Initially, dp[0] is 0 (since a sum of 0 is divisible by three) and the other elements are set to a very low number to indicate that those remainders have not been achieved. For each number in the input list, we compute new possible sums for each remainder by adding this number to the existing sums. We update our dp array accordingly while ensuring that we do not override the results of the current iteration with the updated values immediately. Finally, dp[0] will contain the maximum sum divisible by three.

Code Solutions

# Python Solution
def maxSumDivThree(nums):
    # Initialize dp array where:
    # dp[0]: maximum sum with remainder 0 (divisible by three)
    # dp[1]: maximum sum with remainder 1
    # dp[2]: maximum sum with remainder 2
    dp = [0, float('-inf'), float('-inf')]
    
    # Process each number in the list
    for num in nums:
        # Create a copy of current dp to update new states
        current = dp.copy()
        # Iterate through each remainder state in the current dp
        for i in range(3):
            # Calculate new remainder when adding the current number
            new_remainder = (i + num) % 3
            # Update dp for the new remainder with the maximum possible sum
            dp[new_remainder] = max(dp[new_remainder], current[i] + num)
    # dp[0] holds the maximum sum divisible by three
    return dp[0]

# Example usage:
# print(maxSumDivThree([3,6,5,1,8]))  # Expected output: 18
← Back to All Questions