Welcome to Subscribe On Youtube
1262. Greatest Sum Divisible by Three
Description
Given an integer array nums, return 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 * 1041 <= nums[i] <= 104
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ as the maximum sum of several numbers selected from the first $i$ numbers, such that the sum modulo $3$ equals $j$. Initially, $f[0][0]=0$, and the rest are $-\infty$.
For $f[i][j]$, we can consider the state of the $i$th number $x$:
- If we do not select $x$, then $f[i][j]=f[i-1][j]$;
- If we select $x$, then $f[i][j]=f[i-1][(j-x \bmod 3 + 3)\bmod 3]+x$.
Therefore, we can get the state transition equation:
\[f[i][j]=\max\{f[i-1][j],f[i-1][(j-x \bmod 3 + 3)\bmod 3]+x\}\]The final answer is $f[n][0]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $nums$.
Note that the value of $f[i][j]$ is only related to $f[i-1][j]$ and $f[i-1][(j-x \bmod 3 + 3)\bmod 3]$, so we can use a rolling array to optimize the space complexity, reducing the space complexity to $O(1)$.
-
class Solution { public int maxSumDivThree(int[] nums) { int n = nums.length; final int inf = 1 << 30; int[][] f = new int[n + 1][3]; f[0][1] = f[0][2] = -inf; for (int i = 1; i <= n; ++i) { int x = nums[i - 1]; for (int j = 0; j < 3; ++j) { f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x); } } return f[n][0]; } } -
class Solution { public: int maxSumDivThree(vector<int>& nums) { int n = nums.size(); const int inf = 1 << 30; int f[n + 1][3]; f[0][0] = 0; f[0][1] = f[0][2] = -inf; for (int i = 1; i <= n; ++i) { int x = nums[i - 1]; for (int j = 0; j < 3; ++j) { f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x); } } return f[n][0]; } }; -
class Solution: def maxSumDivThree(self, nums: List[int]) -> int: n = len(nums) f = [[-inf] * 3 for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(nums, 1): for j in range(3): f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x) return f[n][0] -
func maxSumDivThree(nums []int) int { n := len(nums) const inf = 1 << 30 f := make([][3]int, n+1) f[0] = [3]int{0, -inf, -inf} for i, x := range nums { i++ for j := 0; j < 3; j++ { f[i][j] = max(f[i-1][j], f[i-1][(j-x%3+3)%3]+x) } } return f[n][0] } -
function maxSumDivThree(nums: number[]): number { const n = nums.length; const inf = 1 << 30; const f: number[][] = Array(n + 1) .fill(0) .map(() => Array(3).fill(-inf)); f[0][0] = 0; for (let i = 1; i <= n; ++i) { const x = nums[i - 1]; for (let j = 0; j < 3; ++j) { f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - (x % 3) + 3) % 3] + x); } } return f[n][0]; }