সমস্যা বিবরণ
একটি অ্যারে এবং একটি সংখ্যা k দেওয়া আছে। দেওয়া অ্যারেকে k বার রিপিট করে একটি নতুন অ্যারে তৈরি করতে হবে এবং সেটি থেকে সর্বোচ্চ সাবঅ্যারে যোগফল বের করতে হবে।
উদাহরণ
ইনপুট - অ্যারে = {3, 5, 1}, k = 2
আউটপুট - 18
ব্যাখ্যা -
k বার রিপিট করলে অ্যারে = {3, 5, 1, 3, 5, 1}
সর্বোচ্চ সাবঅ্যারে যোগফল = 3+5+1+3+5+1 = 18
সমাধানের পদ্ধতি
প্রথমে অ্যারের সব এলিমেন্টের যোগফল বের করুন। তারপর যোগফলের চিহ্ন অনুযায়ী সাবঅ্যারে যোগফল নির্ণয় করুন:
- যদি যোগফল > 0 হয়, তবে পুরো অ্যারের যোগফলকে k দিয়ে গুণ করুন।
- যদি যোগফল < 0 হয়, তবে দুটি অ্যারে রিপিট করে সর্বোচ্চ সাবঅ্যারে যোগফল বের করুন।
C++ কোড উদাহরণ
#include<iostream>
using namespace std;
void repeatArray(int *arr, int *b, int k, int len) {
int j = 0;
while (k > 0) {
for (int i = 0; i < len; i++)
b[j++] = arr[i];
k--;
}
}
long subArraySum(int *a, int len) {
int max = 0;
long newmax = 0;
for (int i = 0; i < len; i++) {
newmax = newmax + a[i];
if (max < newmax)
max = newmax;
if (newmax < 0)
newmax = 0;
}
return max;
}
long findMaxSubArraySum(int *arr, int k, int len) {
int arraySum = 0;
long maxSum = 0;
int b[(2 * len)] = {0};
repeatArray(arr, b, 2, len);
for (int i = 0; i < len; i++)
arraySum += arr[i];
maxSum = subArraySum(b, 2 * len);
if (arraySum > 0)
maxSum = subArraySum(b, 2 * len) + (k - 2) * arraySum;
return maxSum;
}
int main() {
int arr[] = {3, 5, 1};
int length = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "The maximum subarray sum in array formed by repeating the given array " << k << " times is " << findMaxSubArraySum(arr, k, length);
return 0;
}
আউটপুট
The maximum subarray sum in array formed by repeating the given array 3 times is 27
