Greatest Sum Divisible By Three - Leetcode Solution

Problem Statement: Given an array of integers nums, find the maximum possible sum of a non-empty subarray of nums that is divisible by 3.

Examples: Input: [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6 and 9 their sum is 18 which is a multiple of 3.

Input: [8,6,7,2,1] Output: 18 Explanation: Pick numbers 8, 6 and 4 their sum is 18 which is a multiple of 3.

Solution: To solve this problem, we can use dynamic programming approach. We need to keep track of three states of the subarray sum: sum of subarray divided by 3 with remainder 0, 1 and 2.

We can use an array dp of size 3 to represent these states. Initially, set dp[0] = 0, dp[1] = 0 and dp[2] = 0.

Then we iterate over the array of nums, and for each element, we update the dp array as follows:

• If nums[i]%3 == 0, then we update dp[0] = dp[0] + nums[i]. This is because adding nums[i] to any sum that is divisible by 3 will result in a sum that is still divisible by 3.
• If nums[i]%3 == 1, then we update dp[2] = max(dp[2], dp[0] + nums[i]). This is because adding nums[i] to any sum that is divisible by 3 with remainder 1 will result in a sum that is divisible by 3 with remainder 2, which is the reason we update dp[2].
• If nums[i]%3 == 2, then we update dp[1] = max(dp[1], dp[0] + nums[i]). This is because adding nums[i] to any sum that is divisible by 3 with remainder 2 will result in a sum that is divisible by 3 with remainder 1, which is the reason we update dp[1].

After iterating over all elements of nums, dp[0] will represent the maximum possible sum of a non-empty subarray of nums that is divisible by 3.

Therefore, we return dp[0]. If dp[0] is 0, then it means there is no non-empty subarray that is divisible by 3.

Time Complexity: O(N), where N is the size of the nums array.

Space Complexity: O(1), as we are using constant extra space.

Code:

int maxSumDivThree(vector<int>& nums) { int n = nums.size(); int dp[3] = {0, 0, 0}; for(int i=0; i<n; i++){ if(nums[i]%3 == 0){ dp[0] = dp[0] + nums[i]; dp[1] = dp[1] + nums[i]; dp[2] = dp[2] + nums[i]; } else if(nums[i]%3 == 1){ int temp = dp[0]; dp[0] = max(dp[0], dp[2] + nums[i]); dp[2] = max(dp[2], temp + nums[i]); dp[1] = max(dp[1], dp[1] + nums[i]); } else if(nums[i]%3 == 2){ int temp = dp[0]; dp[0] = max(dp[0], dp[1] + nums[i]); dp[1] = max(dp[1], temp + nums[i]); dp[2] = max(dp[2], dp[2] + nums[i]); } } return dp[0]; }

1