C++-এ ইন্টিজার ব্রেক

একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া আছে। এটিকে কমপক্ষে দুটি ধনাত্মক সংখ্যার যোগফলে ভাঙতে হবে যেন تلك সংখ্যাগুলোর গুণফল সর্বোচ্চ হয়। সেই সর্বোচ্চ গুণফল বের করতে হবে। উদাহরণ: ১০ হলে উত্তর ৩৬, কারণ 10 = 3 + 3 + 4, 3*3*4 = 36।

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

• solve() মেথড বানান যা n, dp অ্যারে আর flag নেবে:
  • যদি n == 0, ১ ফেরত দিন।
  • যদি dp[n] != -1, dp[n] ফেরত দিন।
  • end := (flag ? n-1 : n)
  • ret := 0
  • i = 1 থেকে end পর্যন্ত: ret := max(ret, i * solve(n-i, dp, false))
  • dp[n] := ret ফেরত দিন।
• মূল মেথড থেকে dp আকার n+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