可被三整除的最大和—leetcode1262

給你一個整數數組 

nums

，請你找出并傳回能被三整除的元素最大和。

示例 1：

輸入：nums = [3,6,5,1,8]
輸出：18
解釋：選出數字 3, 6, 1 和 8，它們的和是 18（可被 3 整除的最大和）。
           

示例 2：

輸入：nums = [4]
輸出：0
解釋：4 不能被 3 整除，是以無法選出數字，傳回 0。
           

示例 3：

輸入：nums = [1,2,3,4,4]
輸出：12
解釋：選出數字 1, 3, 4 以及 4，它們的和是 12（可被 3 整除的最大和）。
           

提示：

• 1 <= nums.length <= 4 * 10^4

• 1 <= nums[i] <= 10^4

 方法一：貪心做法

如果一開始數組中所有的數字和是3的倍數的話，那麼就直接輸出就可以了。

如果一開始數組中所有的數字和取餘3等于1的話，有兩種情況：

①減去一個取餘3為1的數字

②減去兩個取餘3為2的數字

這兩種情況取最優

如果一開始數組中所有的數字和取餘3等于2的話，有兩種情況：

①減去一個取餘3為2的數字

②減去兩個取餘3為1的數字

這兩種情況取最優

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int N = nums.size();
        vector<int> div1,div2,div3;\
        int sum = 0;
        for(int i=0;i<N;++i){
            if(nums[i]%3==0)
                div3.push_back(nums[i]);
            else if(nums[i]%3==1)
                div1.push_back(nums[i]);
            else if(nums[i]%3==2)
                div2.push_back(nums[i]);
            sum += nums[i];
        }
        if(sum%3==0)
            return sum;
        else if(sum%3==1){
            if(div2.size()<2 && div1.empty())
                return 0;
            else if(div2.size()<2){
                sort(div1.begin(),div1.end());
                return sum-div1[0];
            }else if(div1.empty()){
                sort(div2.begin(),div2.end());
                return sum-div2[0]-div2[1];
            }else{
                sort(div1.begin(),div1.end());
                sort(div2.begin(),div2.end());
                return max(sum-div2[0]-div2[1],sum-div1[0]);
            }
        }else if(sum%3==2){
            if(div1.size()<2 && div2.empty())
                return 0;
            else if(div1.size()<2){
                sort(div2.begin(),div2.end());
                return sum-div2[0];
            }else if(div2.empty()){
                sort(div1.begin(),div1.end());
                return sum-div1[0]-div1[1];
            }else{
                sort(div1.begin(),div1.end());
                sort(div2.begin(),div2.end());
                return max(sum-div1[0]-div1[1],sum-div2[0]);
            }
        }
        return sum;
    }
};
           

方法二：動态規劃

分析這個樣例可以知道，這是一道01背包的問題。每個數隻能選一次。

不過，樣例裡面還有1，8被選進去。這是因為 1%3 = 1, 8%3 = 2. 也就是說，對于被3整除的最大和，還需要考慮被1和2整除的最大和，并且每個數隻能使用一次。

是以，狀态就出來了：

dp[i][j]表示前 i 個數中模 3 餘 j 的最大和。

一開始dp[0][1]和dp[0][2]都初始化為INT_MIN.

下面上dp打表的圖。

狀态轉移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][*] + nums[i-1]); ( * 根據情況而定)

比如 t%3 == 2

對于dp[i][0]，有前兩種狀态可以遞推得到：

1. dp[i-1][1] + t
2. dp[i-1][0]

從這兩種狀态中取最大值，就是前 i 個數中%3==0的最大和。

在上述式子中，我們也需要保證dp[i-1][1]是最大的，是以我們要寫3個dp，并且要分類讨論。

下面上代碼：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        int dp[n+2][3];
        memset(dp,0,sizeof(dp));
        dp[0][0] = 0; dp[0][1] = INT_MIN; dp[0][2] = INT_MIN;
        for(int i = 1;i <= n;i++)
        {
            int t = nums[i-1]%3;
            if(t == 0)
            {
                dp[i][0] = max(dp[i-1][0], dp[i-1][0] + nums[i-1]);
                dp[i][1] = max(dp[i-1][1], dp[i-1][1] + nums[i-1]);
                dp[i][2] = max(dp[i-1][2], dp[i-1][2] + nums[i-1]);
            }
            else if(t == 1)
            {
                dp[i][0] = max(dp[i-1][0], dp[i-1][2] + nums[i-1]);
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] + nums[i-1]);
                dp[i][2] = max(dp[i-1][2], dp[i-1][1] + nums[i-1]);
            }
            else if(t == 2)
            {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i-1]);
                dp[i][1] = max(dp[i-1][1], dp[i-1][2] + nums[i-1]);
                dp[i][2] = max(dp[i-1][2], dp[i-1][0] + nums[i-1]);
            }
        }
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= 2;j++)
            {
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }

        return dp[n][0];
    }
};