[Leetcode] 1262. Greatest Sum Divisible by Three

배열의 원소들을 골라 더했을 때 3으로 나눈 나머지가 0 이 되는 최대값을 찾아내는 문제. 나머지가 0, 1, 2인 경우의 수를 전부 구해야 하며 이전값 + 현재값 -> 새로운 누산값 이 되는 형태이므로 메모이제이션이 필수적으로 들어간다.

function maxSumDivThree(nums: number[]): number {
    const dp = [0, -1, -1];

    for (const num of nums) {
        const temp = [...dp]

        for (let i = 0; i < 3; i++) {
            if (dp[i] === -1) {
                continue;
            }

            const newSum = dp[i] + num;
            const newModulo = newSum % 3;

            temp[newModulo] = Math.max(temp[newModulo], newSum);
        }

        dp[0] = temp[0]
        dp[1] = temp[1]
        dp[2] = temp[2]
    }

    return dp[0]
};