Greatest Sum Divisible by Three
给一个数组, 求用其中的数组成的最大的和能被3整除. 这个题是dp题, 设max[i]为余数等于i的组成的最大数的数. 那么我们每个数都试一下, 看看他的余数和max[i]组成的新数组cur[i]是否比以前大. 通过不断更新max[i]找到答案. 现在的问题就变成了, 如何找到状态转移方程式, 这里, 我们想要的状态方程是找到新的max和旧的cur的关系. 这个关系是当我们遇到一个新的数字的时候, 我们更新那些数字呢? 通过观察我们知道, 当我们遇到一个新的数字, 我们需要更新这个数字的余数+数组的余数后, 新的数所在的值. 即cur[(i + n) % 3] = Math.max(max[(i + n) % 3], max[i] + n) where i = 1..k
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public int maxSumDivThree(int[] nums) { int[] max = new int[]{0, -10000, -10000}; for (int n : nums) { int[] cur = new int[3]; for (int i = 0; i < 3; i++){ cur[(i + n) % 3] = Math.max(max[(i + n) % 3], max[i] + n); } max = cur; } return max[0]; } } |