Greatest Sum Divisible by Three

Description

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

 

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

 

Constraints:

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

Solution(javascript)

/*
 * @lc app=leetcode id=1262 lang=javascript
 *
 * [1262] Greatest Sum Divisible by Three
 */

// // @lc code=start
// /** Top-down
//  * @param {number[]} nums
//  * @return {number}
//  */
// const maxSumDivThree = function (nums) {
//   const memo = {}
//   const aux = (index, sum) => {
//     memo[index] = memo[index] || {}
//     if (memo[index][sum] !== undefined) {
//       return memo[index][sum]
//     }
//     if (index > nums.length - 1) {
//       return sum % 3 === 0 ? sum : 0
//     }

//     memo[index][sum] = Math.max(
//       aux(index + 1, sum + nums[index]),
//       aux(index + 1, sum),
//     )
//     return memo[index][sum]
//   }
//   return aux(0, 0)
// }

// @lc code=start
/** Top-down
 * @param {number[]} nums
 * @return {number}
 */
const maxSumDivThree = function (nums) {
  let sum = 0
  let one = Infinity
  let two = Infinity
  for (const num of nums) {
    sum += num
    if (num % 3 === 1) {
      two = Math.min(two, num + one)
      one = Math.min(one, num)
    }
    if (num % 3 === 2) {
      one = Math.min(one, two + num)
      two = Math.min(two, num)
    }
  }
  if (sum % 3 === 0) {
    return sum
  }
  if (sum % 3 === 1) {
    return sum - one
  }
  return sum - two
}