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

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];
    }
}