Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1262.html
1262. Greatest Sum Divisible by Three (Medium)
Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.
Example 1:
Input: nums = [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4] Output: 0 Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3:
Input: nums = [1,2,3,4,4] Output: 12 Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
Constraints:
1 <= nums.length <= 4 * 10^41 <= nums[i] <= 10^4
Related Topics:
Dynamic Programming
Solution 1. DP
Let dp[i + 1][r] be the maximum possible sum on the subarray A[0..i] where the current sum modulo 3 is equal to r.
Initially dp[0][0] = 0, dp[0][1] = dp[0][2] = -INF meaning they are invalid states.
dp[i + 1][j] = max(
dp[i][j], // if we skip A[i]
A[i] + dp[i][(j + 3 - A[i] % 3) % 3] // if we pick A[i]
)
The result is dp[N][0].
// OJ: https://leetcode.com/problems/greatest-sum-divisible-by-three/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int maxSumDivThree(vector<int>& A) {
int dp[40001][3] = {}, N = A.size();
dp[0][1] = dp[0][2] = INT_MIN;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < 3; ++j) dp[i + 1][j] = max(dp[i][j], A[i] + dp[i][(j + 3 - A[i] % 3) % 3]);
}
return dp[N][0];
}
};
Solution 2. DP with Space Optimization
// OJ: https://leetcode.com/problems/greatest-sum-divisible-by-three/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxSumDivThree(vector<int>& A) {
array<int, 3> dp = { 0, INT_MIN, INT_MIN }, tmp;
for (int n : A) {
tmp = dp;
for (int j = 0; j < 3; ++j) dp[j] = max(tmp[j], n + tmp[(j + 3 - n % 3) % 3]);
}
return dp[0];
}
};
-
class Solution { public int maxSumDivThree(int[] nums) { if (nums == null || nums.length == 0) return 0; Arrays.sort(nums); int sum = 0; List<Integer> ones = new ArrayList<Integer>(); List<Integer> twos = new ArrayList<Integer>(); int length = nums.length; for (int i = 0; i < length; i++) { int num = nums[i]; sum += num; if (num % 3 == 1) ones.add(num); else if (num % 3 == 2) twos.add(num); } if (sum % 3 == 0) return sum; int onesSize = ones.size(), twosSize = twos.size(); if (sum % 3 == 1) { if (onesSize >= 1 && twosSize >= 2) { int min = Math.min(ones.get(0), twos.get(0) + twos.get(1)); int greatestSum = sum - min; return greatestSum; } else if (onesSize >= 1) { int greatestSum = sum - ones.get(0); return greatestSum; } else if (twosSize >= 2) { int greatestSum = sum - twos.get(0) - twos.get(1); return greatestSum; } else return 0; } else { if (onesSize >= 2 && twosSize >= 1) { int min = Math.min(ones.get(0) + ones.get(1), twos.get(0)); int greatestSum = sum - min; return greatestSum; } else if (onesSize >= 2) { int greatestSum = sum - ones.get(0) - ones.get(1); return greatestSum; } else if (twosSize >= 1) { int greatestSum = sum - twos.get(0); return greatestSum; } else return 0; } } } ############ class Solution { public int maxSumDivThree(int[] nums) { int[] f = new int[3]; for (int x : nums) { int a = f[0] + x, b = f[1] + x, c = f[2] + x; f[a % 3] = Math.max(f[a % 3], a); f[b % 3] = Math.max(f[b % 3], b); f[c % 3] = Math.max(f[c % 3], c); } return f[0]; } } -
// OJ: https://leetcode.com/problems/greatest-sum-divisible-by-three/ // Time: O(N) // Space: O(N) class Solution { public: int maxSumDivThree(vector<int>& A) { int dp[40001][3] = {}, N = A.size(); dp[0][1] = dp[0][2] = INT_MIN; for (int i = 0; i < N; ++i) { for (int j = 0; j < 3; ++j) dp[i + 1][j] = max(dp[i][j], A[i] + dp[i][(j + 3 - A[i] % 3) % 3]); } return dp[N][0]; } }; -
class Solution: def maxSumDivThree(self, nums: List[int]) -> int: dp = [0] * 3 for v in nums: a, b, c = dp[0] + v, dp[1] + v, dp[2] + v dp[a % 3] = max(dp[a % 3], a) dp[b % 3] = max(dp[b % 3], b) dp[c % 3] = max(dp[c % 3], c) return dp[0] ############ # 1262. Greatest Sum Divisible by Three # https://leetcode.com/problems/greatest-sum-divisible-by-three/ class Solution: def maxSumDivThree(self, nums: List[int]) -> int: n = len(nums) dp = [0, 0, 0] for num in nums: for i in dp[:]: dp[(i+num)%3] = max(dp[(i+num)%3], num + i) return dp[0] -
func maxSumDivThree(nums []int) int { f := [3]int{} for _, x := range nums { a, b, c := f[0]+x, f[1]+x, f[2]+x f[a%3] = max(f[a%3], a) f[b%3] = max(f[b%3], b) f[c%3] = max(f[c%3], c) } return f[0] } func max(a, b int) int { if a > b { return a } return b }