C++-এ তিন দিয়ে বিভাজ্য সর্বোচ্চ যোগফল

একটি পূর্ণসংখ্যা অ্যারে nums দেওয়া আছে। আমাদের এমন সর্বোচ্চ সম্ভাব্য উপাদানগুলোর যোগফল বের করতে হবে যেটি ৩ দিয়ে বিভাজ্য। উদাহরণস্বরূপ, ইনপুট [3,6,5,1,8] হলে আউটপুট হবে ১৮, কারণ উপ-অ্যারে [3,6,1,8]-র যোগফল ১৮ যা ৩ দিয়ে বিভাজ্য।

সমাধানের ধাপগুলো:

n := nums অ্যারের সাইজ।
(n + 1) x 3 আকারের একটি ২D অ্যারে dp তৈরি করুন।
dp[0, 0] := 0, dp[0,1] := -inf, dp[0,2] := -inf সেট করুন।
i = 1 থেকে n পর্যন্ত লুপ চালান:
- x := nums[i - 1]
- j = 0 থেকে 2 পর্যন্ত: dp[i, j] := dp[i - 1, j]
- j = 0 থেকে 2 পর্যন্ত:
  - k := (x + j) mod 3
  - dp[i, k] := max(dp[i, k], dp[i - 1, j] + x)
dp[n, 0] ফেরত দিন।

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int maxSumDivThree(vector<int>& nums) {       int n = nums.size();       int dp[n+1][3];       dp[0][0] = 0;       dp[0][1] = INT_MIN;       dp[0][2] = INT_MIN;       for(int i = 1; i <= n; i++){          int x = nums[i-1];          for(int j = 0; j < 3; j++)dp[i][j] = dp[i-1][j];          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];    } }; main(){    vector<int> v = {3,6,5,1,8};    Solution ob;    cout << (ob.maxSumDivThree(v)); }

ইনপুট

[3,6,5,1,8]