#1262 - Greatest Sum Divisible by Three

Medium • View on LeetCode • View on GitHub

Array Dynamic Programming Sorting Greedy

Problem Description

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumDivThree = function(nums) {
  const dp = [0, -Infinity, -Infinity];

  for (const num of nums) {
    const prev = [...dp];
    for (let remainder = 0; remainder < 3; remainder++) {
      dp[(remainder + num) % 3] = Math.max(dp[(remainder + num) % 3], prev[remainder] + num);
    }
  }

  return dp[0];
};