README
¶
Greatest Sum Divisible by Three
动态规划
使用动态规划解题，用 dp [3]int 分别代表 mod 3 为 0，1，2 的最大值。
防止 dp 自更新，需要 temp 存储上一轮 dp 的值。
0 不能作为模 1、2 的初始值，可以用一个比较小的值标记，这样初始值 + 当前值不会超过 dp[0] 就行。
Documentation
¶
Overview ¶
* @lc app=leetcode id=1262 lang=golang * * [1262] Greatest Sum Divisible by Three * * https://leetcode.com/problems/greatest-sum-divisible-by-three/description/ * * algorithms * Medium (43.02%) * Likes: 246 * Dislikes: 7 * Total Accepted: 8.3K * Total Submissions: 19.2K * Testcase Example: '[3,6,5,1,8]' * * 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 * *
Source Files