ผลรวมสูงสุดที่หารด้วย 3 ลงตัวใน C++

ให้อาร์เรย์ nums ของจำนวนเต็ม ต้องการหาผลรวมสูงสุดของสมาชิกในอาร์เรย์ที่หารด้วย 3 ลงตัว ตัวอย่างเช่น อินพุต [3,6,5,1,8] ผลลัพธ์คือ 18 เพราะเลือกย่อยอาร์เรย์ [3,6,1,8] ได้ผลรวม 18 ซึ่งหารด้วย 3 ลงตัว

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. n := ขนาดของอาร์เรย์ nums
2. สร้างตาราง DP ขนาด (n + 1) x 3 โดย dp[i][j] เก็บผลรวมสูงสุดจาก i ตัวแรกที่ modulo 3 ได้ j
3. กำหนดค่าเริ่มต้น: dp[0][0] = 0, dp[0][1] = -inf, dp[0][2] = -inf
4. วนลูป i จาก 1 ถึง n:
   • x := nums[i - 1]
   • คัดลอกค่าเดิม: dp[i][j] := dp[i-1][j] สำหรับ j = 0,1,2
   • ลองนำ x มารวม: สำหรับ j = 0,1,2 คำนวณ k = (x + j) % 3 แล้วอัปเดต dp[i][k] = max(dp[i][k], dp[i-1][j] + x)
5. คืนค่า dp[n][0]

ตัวอย่างโค้ด 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);
}

Input

[3,6,5,1,8]

Output

18