Readme

1262.Greatest-Sum-Divisible-by-Three

解法1：数学

我们将所有的数字分为三类，有a个被3整除的，有b个被3除余1的，有c个被3除余2的。显然所有的被3整除的数都可以用。剩下两类的数字我们分别取多少呢？我们可以枚举一下配对的可能：前者的数目m可以是b,b-1,b-2，后者的数目n可以是c,c-1,c-2.配对成功的要求是(1*m+2*n)%3==0. 如果配对成功，我们自然取的是被3除余1的最大的m个数、被3除余2的最大的n个数。

解法2：动态规划

令dp[i][j]表示前i个元素里能取到的最大的sum，使得sum被3除的余数是j。

对于dp[i][j]而言，针对nums[i]有两种决策：

1. 不取nums[i]，那么dp[i][j] = dp[i-1][j]
2. 取nums[i]，那么dp[i][j] = dp[i-1][(j-nums[i]%3+3)%3]+nums[i]

最终的答案就是dp[n-1][0]