ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে সংখ্যা আছে, আমাদের প্রদত্ত অ্যারের উপাদানগুলির সর্বাধিক সম্ভাব্য যোগফল খুঁজে বের করতে হবে যাতে এটি তিনটি দ্বারা বিভাজ্য হয়। সুতরাং যদি ইনপুটটি [3,6,5,1,8] এর মত হয়, তাহলে আউটপুট হবে 18, যেমন সাব্যারে [3,6,1,8], এবং যোগফল 18, যা 3 দ্বারা বিভাজ্য .
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=সংখ্যা অ্যারের আকার
- একটি 2d অ্যারে ডিপি আকারের (n + 1) x 3 তৈরি করুন
- dp[0, 0] সেট করুন :=0, dp[0,1] :=-inf, dp[0,2] :=inf
- আমি 1 থেকে n রেঞ্জের জন্য;
- x :=সংখ্যা[i - 1]
- 0 থেকে 2, dp[i, j] :=dp[i – 1, j] পরিসরে j-এর জন্য
- 0 থেকে 2
- পরিসরে j এর জন্য
- k :=(x + j) মোড 3
- dp[i, k] :=সর্বাধিক 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]
আউটপুট
18
