1262. 可被三整除的最大和

LC每日一题，参考1262. 可被三整除的最大和，难度分1762。

题目

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

解题思路

• 贪心：反向思考,求和后减去一些比较小的数使和最大。
• 动态规划：定义dp[i][j]表示[0,i)中余数为j的最大和,找转移方程。

贪心

class Solution {
    public int maxSumDivThree(int[] nums) {
        int sum = 0;
        //计算最小的两个余数1和最小的两个余数2
        int pre1 = 0,pre2 = 0,pre3 = 0,pre4 = 0;
        for(int i : nums) {
            sum += i;
            if(i%3 == 1) {
                if(pre1 == 0) pre1 = i;
                else {
                    if(i < pre1) {
                        if(pre2 == 0) pre2 = pre1;
                        else pre2 = Math.min(pre1,pre2);
                        pre1 = i;
                    }else {
                        if(pre2 == 0) pre2 = i;
                        else pre2 = Math.min(i,pre2);
                    }
                }
            }
            else if(i%3 == 2){
                if(pre3 == 0) pre3 = i;
                else {
                    if(i < pre3) {
                        if(pre4 == 0) pre4 = pre3;
                        else pre4 = Math.min(pre3,pre4);
                        pre3 = i;
                    }else {
                        if(pre4 == 0) pre4 = i;
                        else pre4 = Math.min(i,pre4);
                    }
                }
            }
        }
        if(sum%3 == 0) return sum;
        int min = sum;
        if(sum%3 == 1) {
            if(pre1 > 0) min = Math.min(min,pre1);
            if(pre3 > 0 && pre4 > 0) min = Math.min(min,pre3+pre4);
        }else {
            if(pre1 > 0 && pre2 > 0) min = Math.min(min,pre1+pre2);
            if(pre3 > 0) min = Math.min(min,pre3);
        }
        return sum - min;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度,一重循环遍历。
• 空间复杂度：O(1)。

动态规划

class Solution {
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        //动态规划 dp[i][j]表示前i个数余数为j的最大值
        int[][] dp = new int[n+1][3];
        dp[0][1]=Integer.MIN_VALUE; // 不合法设为负无穷
        dp[0][2]=Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            // if(nums[i]%3 == 0){
            //     for(int j = 0; j < 3; j++) dp[i+1][j] = dp[i][j] + nums[i];
            // }else if(nums[i]%3 == 1) {
            //     dp[i+1][0] = Math.max(dp[i][0],dp[i][2]+nums[i]);
            //     dp[i+1][1] = Math.max(dp[i][1],dp[i][0]+nums[i]);
            //     dp[i+1][2] = Math.max(dp[i][2],dp[i][1]+nums[i]);
            // }else {
            //     dp[i+1][0] = Math.max(dp[i][0],dp[i][1]+nums[i]);
            //     dp[i+1][1] = Math.max(dp[i][1],dp[i][2]+nums[i]);
            //     dp[i+1][2] = Math.max(dp[i][2],dp[i][0]+nums[i]);
            // }
            for(int j = 0; j < 3; j++){
                //选或不选取最大值递推
                dp[i+1][j] = Math.max(dp[i][j],dp[i][(j-nums[i]%3 + 3)%3]+nums[i]);
            }
        }
        return dp[n][0];
    }
}

复杂度分析

• 时间复杂度：O(n)，一重循环遍历。
• 空间复杂度：O(n)，dp数组空间。

2023.06.19