C++ में पूर्णांक विभाजन

मान लीजिए हमारे पास एक धनात्मक पूर्णांक n है, हमें इसे कम से कम दो धनात्मक संख्याओं के योग में विभाजित करना है और उन पूर्णांकों के गुणनफल को अधिकतम करना है। हमें अधिकतम गुणनफल ढूंढना है जो हम प्राप्त कर सकते हैं।

उदाहरण के लिए, यदि संख्या 10 है, तो उत्तर 36 होगा, जैसे 10 = 3 + 3 + 4, 3 * 3 * 4 = 36।

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

• solve() नामक एक विधि परिभाषित करें, यह n, सरणी dp और flag लेगा
• यदि n = 0, तो 1 लौटाएं
• यदि dp[n] -1 नहीं है, तो dp[n] लौटाएं
• end := n - 1 जब flag सेट हो, अन्यथा n
• ret := 0
• i को 1 से end तक लूप करें
  • ret := ret और i * solve(n - i, dp, गलत) का अधिकतम
• dp[n] := ret सेट करें और लौटाएं
• मुख्य विधि से, आकार n + 1 की एक सरणी dp बनाएं और इसे -1 से भरें
• solve(n, dp) लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int solve(int n, vector <int>& dp, bool flag = true){       if(n == 0) return 1;       if(dp[n] != -1) return dp[n];       int end = flag? n - 1: n;       int ret = 0;       for(int i = 1; i <= end; i++){          ret = max(ret, i * solve(n - i, dp, false));       }       return dp[n] = ret;    }    int integerBreak(int n) {       vector <int>dp(n + 1, -1);       return solve(n, dp);    } }; main(){    Solution ob;    cout << (ob.integerBreak(10)); }

इनपुट

10

आउटपुट

36