Mind palace

some thoughts

0%

1262. Greatest Sum Divisible by Three

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

dp O(n) time O(1) space
思考过程
f[0] f[1] f[2]分别表示到当前数为止模3结果为0 1 2的最大和
0可以由0 + 0，1 + 2， 2 + 1生成
1可以由0 + 1, 1 + 0, 2 + 2生成
2可以由0 + 2， 1 + 1， 2 + 0生成
用这个
每得到一个新结果就尝试去更新对应的最大和
下面这种做法的转移方程为
f[{(f[i] + x) % 3}] = max{f[{(f[i] + x) % 3}], f[i] + x}, where i ~ [0, 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f(3); // 要初始化为0，因为后边要做加法
        for (int x : nums) {
            auto t = f;
            for (int y : f) {
                t[(y + x) % 3] = max(t[(y + x) % 3], y + x);
            }
            f = t;
        }
        return f[0];
    }
};

下面这些方法f[1] f[2]必须初始化为无穷小表示不存在，因为最开始一个数都没有是不可能出现余数为1或2的最大和的，上面那种解法初始化为0是因为要用前一次迭代的最大和直接参与计算本次迭代的结果应该给哪个余数下标，算法上有区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f{0, INT_MIN, INT_MIN};
        for (int x : nums) {
            auto t = f;
            for (int i = 0; i < 3; ++i) {
                t[(x + i) % 3] = max(f[(x + i) % 3], f[i] + x);
            }
            f = t;
        }
        return f[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f{0, INT_MIN, INT_MIN};
        for (int x : nums) {
            switch (x % 3) {
                case 0: {
                    f[0] += x;
                    f[1] += x;
                    f[2] += x;
                } break;
                case 1: {
                    auto t = {max(f[0], f[2] + x),
                              max(f[1], f[0] + x),
                              max(f[2], f[1] + x)}; // t的type是initializer_list<int>
                    f = t; // vector<int>的operator=支持initializer_list<int>传参
                } break;
                default: {
                    auto t = {max(f[0], f[1] + x),
                              max(f[1], f[2] + x),
                              max(f[2], f[0] + x)};
                    f = t;
                }
            }
        }
        return f[0];
    }
};

NP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        sort(begin(nums), end(nums));
        t = accumulate(begin(nums), end(nums), 0);
        if (t % 3 == 0) return t;
        dfs(0, nums, 0);
        return res;
    }

    void dfs(int s, const vector<int> &A, int b) {
        for (int i = b; i < A.size(); ++i) {
            s += A[i];
            if (t - s <= res) return;
            if ((t - s) % 3 == 0) {
                res = max(res, t - s);
                return;
            } else {
                dfs(s, A, i + 1);
            }
            s -= A[i];
        }
    }

    int res = 0, t = 0;
};