C++ में तीन से विभाज्य सबसे बड़ा योग

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी संख्या है, हमें दिए गए सरणी के तत्वों का अधिकतम संभव योग इस तरह खोजने की आवश्यकता है कि यह तीन से विभाज्य हो। तो अगर इनपुट [3,6,5,1,8] जैसा है, तो आउटपुट 18 होगा, क्योंकि सबरे [3,6,1,8] है, और योग 18 है, जो 3 से विभाज्य है ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=nums array का आकार
• एक 2d सरणी dp आकार (n + 1) x 3 बनाएं
• सेट डीपी[0, 0]:=0, डीपी[0,1]:=-इन्फ, डीपी[0,2] :=इंफ
• i के लिए 1 से n की सीमा में;
  • x :=nums[i - 1]
  • जे के लिए 0 से 2 की सीमा में, dp[i, j] :=dp[i – 1, j]
  • जे के लिए 0 से 2 की सीमा में
    • k :=(x + j) मॉड 3
    • dp[i, k] :=अधिकतम dp[i, k] और dp[i – 1, j] + x
• रिटर्न डीपी[एन, 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