package leetcode;

/**
 * https://leetcode.com/problems/greatest-sum-divisible-by-three/
 */
public class Problem1262 {
    public int maxSumDivThree(int[] nums) {
        int answer = 0;
        for (int i = 0; i < nums.length; i++) {
            answer = Math.max(answer, maxSumDivThree(nums, i));
        }
        return answer;
    }

    private static int maxSumDivThree(int[] nums, int index) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1262 prob = new Problem1262();
        System.out.println(prob.maxSumDivThree(new int[]{3,6,5,1,8})); // 18
//        System.out.println(prob.maxSumDivThree(new int[]{4})); // 0
//        System.out.println(prob.maxSumDivThree(new int[]{1,2,3,4,4})); // 12
    }
}

package leetcode;

/**
 * https://leetcode.com/problems/greatest-sum-divisible-by-three/
 */
public class Problem1262 {
    public int maxSumDivThree(int[] nums) {
        return maxSumDivThree(nums, 0, 0, new Integer[40001][3]);
    }

    private static int maxSumDivThree(int[] nums, int index, int sum, Integer[][] memo) {
        if (index == nums.length) {
            return 0;
        }
        if (memo[index][sum] != null) {
            return memo[index][sum];
        }
        int max = 0;
        int val = maxSumDivThree(nums, index + 1, sum, memo);
        if ((sum + val) % 3 == 0) {
            max = val;
        }
        val = nums[index] + maxSumDivThree(nums, index + 1, (sum + nums[index]) % 3, memo);
        if ((sum + val) % 3 == 0) {
            max = Math.max(max, val);
        }
        memo[index][sum] = max;
        return max;
    }
}

Solve problem 1262