এই সমস্যায়, আমাদের n সংখ্যক ভিন্ন দৈর্ঘ্যের অ্যারে দেওয়া আছে। আমাদের কাজ হলো m দৈর্ঘ্যের কম বা সমান সর্বোচ্চ যোগফল অ্যারে খুঁজে বের করা।
আমাদের অ্যারেগুলো থেকে সাব-অ্যারে বের করে যোগফল সর্বোচ্চ করতে হবে এবং সব সাব-অ্যারে রের মিলিত দৈর্ঘ্য m হতে হবে।
উদাহরণ
ইনপুট
n = 3, m = 4
arrOfArr[][] = {
{5, 2, -1, 4, -3}
{3, -2, 1, 6}
{-2, 0, 5}
}
আউটপুট
20
ব্যাখ্যা
সাব-অ্যারেগুলো: {5, 4}, {6}, {5}, দৈর্ঘ্য = 2 + 1 + 1 = 4
যোগফল = 5 + 4 + 6 + 5 = 20
সমাধানের পদ্ধতি
সমস্যাটি ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। আমরা একটি DP অ্যারে তৈরি করব এবং ক্যুমুলেটিভ অ্যারে সম গণনা করব দৈর্ঘ্য k (০ থেকে m) এর জন্য।
DP অ্যারেতে প্রতিটি অ্যারের জন্য ০ থেকে m দৈর্ঘ্যের সর্বোচ্চ অ্যারে যোগফল সংরক্ষণ করব। শেষে DP অ্যারের শেষ সারি থেকে সর্বোচ্চ যোগফল ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define N 5
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumArray(int arr[][N], int M) {
int DP[N][M];
int sumArray[M];
int sum[M];
memset(DP, -1, sizeof(DP[0][0]) * N * M);
sumArray[0] = 0;
DP[0][0] = 0;
for (int i = 1; i <= 5; i++) {
int len = arr[i - 1][0];
for (int j = 1; j <= len; j++) {
sumArray[j] = arr[i - 1][j];
sumArray[j] += sumArray[j - 1];
sum[j] = -100;
}
for (int j = 1; j <= len && j <= 6; j++)
for (int k = 1; k <= len; k++)
if (j + k - 1 <= len)
sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
for (int j = 0; j <= 6; j++)
DP[i][j] = DP[i - 1][j];
for (int j = 1; j <= 6; j++)
for (int cur = 1; cur <= j && cur <= len; cur++)
DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
}
int maxSum = 0;
for (int i = 0; i <= 6; i++)
maxSum = findMax(maxSum, DP[5][i]);
return maxSum;
}
int main() {
int arr[][N] = { { 3, 2, -1, 6 },
{ 2, 7, -1 },
{ 3, 2, 2, -4 } };
int m = 4;
cout << "Maximum sum array of length less than or equal to " << m << " : " << findMaxSumArray(arr, m);
}
আউটপুট
Maximum sum array of length less than or equal to 4 : 15
