স্প্লিট অ্যারে লার্জেস্ট সাম সমস্যা
একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে এবং একটি মান m দেওয়া আছে। অ্যারেটিকে mটি সংলগ্ন সাবঅ্যারে-এ ভাগ করতে হবে। লক্ষ্য হলো এই mটি সাবঅ্যারেতে যেটির যোগফল সর্বোচ্চ, সেই সর্বোচ্চ যোগফলকে ন্যূনতম করা।
উদাহরণ: [7,2,4,10,9] এবং m = 2 হলে, সাবঅ্যারে [7,2,4] (যোগফল ১৩) এবং [10,9] (যোগফল ১৯)। সর্বোচ্চ যোগফল ১৯, যা ন্যূনতম সম্ভব।
সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
n := v.size()- প্রিফিক্স যোগফল অ্যারে
sumতৈরি করুন - DP টেবিল
dp[i]= সূচকiথেকে শেষ পর্যন্ত বাকি অংশকেkটি সাবঅ্যারে-এ ভাগ করলে ন্যূনতম সম্ভব সর্বোচ্চ যোগফল - প্রথমে
k=1এর জন্যdpইনিশিয়ালাইজ করুন k = 2থেকেmপর্যন্ত আপডেট করুন:dp[start] = min(dp[start], max(sum(end-1) - sum(start-1), dp[end]))
dp[0]ফেরত দিন
C++ কোড উদাহরণ
#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];
}
};
int main() {
Solution ob;
vector<int> v = {7,2,4,10,9};
cout << (ob.splitArray(v, 2));
return 0;
}
ইনপুট
[7,2,4,10,9] 2
আউটপুট
19
