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

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

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• n := nums सरणी का आकार
• आकार (n + 1) x 3 का एक 2D सरणी 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]

आउटपुट

18