Tổng lớn nhất chia hết cho 3 trong C++

Mô tả bài toán

Cho mảng số nguyên nums, tìm tổng lớn nhất của các phần tử (có thể chọn tập con) sao cho tổng chia hết cho 3.

Ví dụ: [3,6,5,1,8] → kết quả 18 (tập con [3,6,1,8], tổng = 18 chia hết cho 3).

Giải thuật Quy hoạch động

Sử dụng mảng DP 2 chiều dp[i][j] = tổng lớn nhất dùng i phần tử đầu có dư j khi chia cho 3.

1. Khởi tạo: dp[0][0]=0, dp[0][1]=dp[0][2]=-INF.
2. Duyệt từng phần tử x = nums[i-1]:
   • Copy giá trị cũ: dp[i][j] = dp[i-1][j].
   • Thử thêm x: k = (x + j) % 3, cập nhật dp[i][k] = max(dp[i][k], dp[i-1][j] + x).
3. Kết quả: dp[n][0].

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<array<int, 3>> dp(n+1);
        dp[0] = {0, INT_MIN, INT_MIN};
        for (int i = 1; i <= n; i++) {
            int x = nums[i-1];
            dp[i] = dp[i-1];
            for (int j = 0; j < 3; j++) {
                int k = (x + j) % 3;
                dp[i][k] = max(dp[i][k], dp[i-1][j] + x);
            }
        }
        return dp[n][0];
    }
};

int main() {
    vector<int> v = {3,6,5,1,8};
    Solution ob;
    cout << ob.maxSumDivThree(v); // 18
    return 0;
}

Độ phức tạp

• Thời gian: O(n) (n = kích thước mảng).
• Không gian: O(n) (có thể tối ưu xuống O(1) dùng 2 mảng kích thước 3).