[leetcode] 1262. Greatest Sum Divisible by Three

[leetcode] 1262. 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: 18Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

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

Example 3:

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

Constraints:

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

分析

题目的意思是：求一个数组中能被3整除的最大子序列。这道题如果用dp的话，可以设置dp[i][k], k<3的数组，表示的是前i个数被3整除余数为k的最大值，这样的话需要考虑k=0,k=1,k=2这三种情况的递推公式：

dp[i][*] = max{dp[i-1][*],dp[i-1][*] + nums[i]} (* 取值为 0,1,2)

分三种情况考虑就行了。最终的结果是dp[n][0] 另外一种做法是用一个一维dp数组表示表示的是前i个数被3整除余数为k的最大值.递推公式为:

dp[(i + num) % 3] = max( dp[(i + num) % 3] , dp[i] + num)

最终得到的结果是dp[0]。想出来还是挺麻烦的，哈哈 我把例1的dp中间结果打印出来：

nums = [3,6,5,1,8][3, 0, 0][9, 0, 0][9, 0, 14][15, 10, 14][18, 22, 23]

自己可以手工推导一下

代码

class Solution: def maxSumDivThree(self, nums: List[int]) -> int: n=len(nums) dp=[0]*(3) for num in nums: dp1=[item for item in dp] for s in dp1: dp[(s+num)%3]=max(dp[(s+num)%3],s+num) return dp[0]

代码二

class Solution: def maxSumDivThree(self, nums): n=len(nums) dp=[0]*(3) for num in nums: dp1=[item for item in dp] for s in dp1: dp[(s+num)%3]=max(dp[(s+num)%3],s+num) print(dp) return dp[0]if __name__ == "__main__": nums = [3,6,5,1,8] solution=Solution() res=solution.maxSumDivThree(nums) print(res)

参考文献

​​花花酱 LeetCode 1262. Greatest Sum Divisible by Three​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。