C++ এ বিভক্ত অ্যারে বৃহত্তম যোগফল

ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে এবং একটি মান m আছে। আমরা এই অ্যারেটিকে m সংখ্যায় সংলগ্ন সাব্যারেতে ভাগ করতে পারি। এই m সাব্যারেগুলির মধ্যে সবচেয়ে বড় যোগফল কমানোর জন্য আমাদের একটি অ্যালগরিদম তৈরি করতে হবে৷

সুতরাং যদি অ্যারে বলা হয় [7,2,4,10,9], এবং m =2, তাহলে যোগফল হবে 19, যেহেতু আমরা [7,2,4] এবং [10,9] এর মতো দুটি সাবয়ারে তৈরি করতে পারি। , তারপর সবচেয়ে বড় যোগফল সহ সাব্যারে হল 19।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন splitArray() সংজ্ঞায়িত করুন, এটি একটি অ্যারে নিয়ে যাবে v, m,
• n :=v এর আকার
• একটি অ্যারে ডিপি আকারের তৈরি করুন
• অন্য একটি অ্যারের যোগফল n আকারের করুন
• সমষ্টি[0] :=v[0]
• আরম্ভ করার জন্য i :=1, যখন i করুন
• সমষ্টি[i] :=যোগফল[i - 1] + v[i]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int splitArray(vector<int>& v, int m) {
      int n = v.size();
      vector <long long int > dp(n);
      vector <long long int> sum(n);
      sum[0] = v[0];
      for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
      dp[0] = sum[n-1];
      for(int i =1;i<n;i++){
         dp[i] = sum[n-1] - sum[i-1];
      }
      for(int i =1;i<m;i++){
         for(int start = 0;start<n-i;start++){
            for(int end = start+1;end<=n-i;end++){
               dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
            }
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<int> v = {7,2,4,10,9};
   cout << (ob.splitArray(v, 2));
}

ইনপুট

[7,2,4,10,9]
2

আউটপুট

19