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

@@ -169,596 +169,697 @@
     
-int answer = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            answer = Math.max(answer, maxSumDivThree(nums, i));%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static int maxSumDivThree(int%5B%5D nums, int index) %7B%0A        // TODO%0A        return 0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1262 prob = new Problem1262();%0A        System.out.println(prob.maxSumDivThree(new int%5B%5D%7B3,6,5,1,8%7D)); // 18%0A//        System.out.println(prob.maxSumDivThree(new int%5B%5D%7B4%7D)); // 0%0A//        System.out.println(prob.maxSumDivThree(new int%5B%5D%7B1,2,3,4,4%7D)); // 12
+return maxSumDivThree(nums, 0, 0, new Integer%5B40001%5D%5B3%5D);%0A    %7D%0A%0A    private static int maxSumDivThree(int%5B%5D nums, int index, int sum, Integer%5B%5D%5B%5D memo) %7B%0A        if (index == nums.length) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Bindex%5D%5Bsum%5D != null) %7B%0A            return memo%5Bindex%5D%5Bsum%5D;%0A        %7D%0A        int max = 0;%0A        int val = maxSumDivThree(nums, index + 1, sum, memo);%0A        if ((sum + val) %25 3 == 0) %7B%0A            max = val;%0A        %7D%0A        val = nums%5Bindex%5D + maxSumDivThree(nums, index + 1, (sum + nums%5Bindex%5D) %25 3, memo);%0A        if ((sum + val) %25 3 == 0) %7B%0A            max = Math.max(max, val);%0A        %7D%0A        memo%5Bindex%5D%5Bsum%5D = max;%0A        return max;
 %0A   

Solve problem 1262