ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে অ্যারে এবং একটি পূর্ণসংখ্যা k আছে, আমাদের কে বার বার পুনরাবৃত্তি করে অ্যারে পরিবর্তন করতে হবে। সুতরাং arr =[1, 2] এবং k =3 হলে পরিবর্তিত অ্যারে হবে [1, 2, 1, 2, 1, 2]।
এখন আমাদের পরিবর্তিত অ্যারেতে সর্বাধিক সাব-অ্যারে যোগফল খুঁজে বের করতে হবে। মনে রাখবেন যে সাব-অ্যারের দৈর্ঘ্য 0 হতে পারে এবং সেক্ষেত্রে এর যোগফল 0 হতে পারে। উত্তরটি অনেক বড় হতে পারে, উত্তর মডিউল 10^9 + 7 খুঁজুন।
সুতরাং ইনপুট যদি [1,-2,1] এবং k =5 এর মত হয়, তাহলে ফলাফল হবে 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
GetKadane() নামক পদ্ধতিটি সংজ্ঞায়িত করুন, এটি অ্যারে নেবে, এটি −
এর মতো কাজ করবে -
ret :=-inf, sum :=0, ret এবং sum-এর সমস্ত মান হবে mod 10^9 + 7
-
i এর জন্য 0 থেকে arr- 1
এর আকার-
যোগফল :=arr[i] এবং arr[i] + যোগফল
-এর সর্বোচ্চ -
ret :=ret এর সর্বোচ্চ, যোগফল
-
-
যদি ret <0 হয়, তাহলে 0 ফেরত দিন, অন্যথায় ret
-
GetSum() নামক পদ্ধতিটি সংজ্ঞায়িত করুন, এটি অ্যারে নেবে, এটি −
এর মতো কাজ করবে -
ret :=0, ret মান হবে mod 10^9 + 7
-
i এর জন্য 0 থেকে arr- 1
এর আকার-
ret :=ret + arr[i]
-
-
রিটার্ন রিটার্ন
-
getPrefix() নামক পদ্ধতিটি সংজ্ঞায়িত করুন, এটি অ্যারে নেবে, এটি −
এর মতো কাজ করবে -
ret :=-inf, sum :=0, ret এবং sum-এর সমস্ত মান হবে mod 10^9 + 7
-
i এর জন্য 0 থেকে arr- 1
এর আকার-
যোগফল :=যোগফল + arr[i]
-
ret :=ret এবং যোগফলের সর্বোচ্চ
-
-
যদি ret <0 হয়, তাহলে 0 ফেরত দিন, অন্যথায় ret
-
getSuffix() নামক পদ্ধতি সংজ্ঞায়িত করুন, এটি অ্যারে নেবে, এটি −
এর মতো কাজ করবে -
ret :=inf, sum :=0, ret এবং sum-এর সমস্ত মান হবে mod 10^9 + 7
-
i এর জন্য arr-এর রেঞ্জ সাইজ - 1 থেকে 0
নিচে-
যোগফল :=যোগফল + arr[i]
-
ret :=ret এবং যোগফলের সর্বোচ্চ
-
-
যদি ret <0 হয়, তাহলে 0 ফেরত দিন, অন্যথায় ret
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
kadane :=getKadane(arr), sum :=getSum(arr), উপসর্গ :=getPrefix(arr), প্রত্যয় :=getSuffix(arr)
-
যদি k 1 হয়, তাহলে কদনে ফেরত দিন
-
যদি যোগফল> 1 হয়, তাহলে সর্বোচ্চ (সমষ্টি * (k - 2)) + উপসর্গ + প্রত্যয় এবং কাদানে ফেরত দিন
-
অন্যথায় (উপসর্গ + প্রত্যয়) এবং কদনে
এর সর্বাধিক ফেরত দিন
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
public:
int getKadane(vector <int>& arr){
int ret = INT_MIN;
int sum = 0;
for(int i = 0; i < arr.size(); i++){
sum = max(arr[i], arr[i] + sum);
ret = max(ret, sum);
sum %= MOD;
ret %= MOD;
}
return ret < 0? 0 : ret;
}
int getSum(vector <int>& arr){
int ret = 0;
for(int i = 0; i < arr.size(); i++){
ret += arr[i];
ret %= MOD;
}
return ret;
}
int getPrefix(vector <int>& arr){
int ret = INT_MIN;
int sum = 0;
for(int i = 0; i <arr.size(); i++){
sum += arr[i];
sum %= MOD;
ret = max(ret, sum);
ret %= MOD;
}
return ret < 0 ? 0 : ret;
}
int getSuffix(vector <int>& arr){
int sum = 0;
int ret = INT_MIN;
for(int i = arr.size() - 1; i >= 0 ; i--){
sum += arr[i];
ret = max(ret, sum);
sum %= MOD;
ret %= MOD;
}
return ret < 0 ? 0 : ret;
}
int kConcatenationMaxSum(vector<int>& arr, int k) {
int kadane = getKadane(arr);
int sum = getSum(arr);
int prefix = getPrefix(arr);
int suffix = getSuffix(arr);
if(k == 1) return kadane;
if(sum > 0){
return max((int)mul((k-2) , sum) + prefix % MOD + suffix % MOD, kadane);
} else {
return max(add(prefix , suffix), kadane);
}
}
};
main(){
vector<int> v1 = {1,-2,1};
Solution ob;
cout << (ob.kConcatenationMaxSum(v1, 5));
} ইনপুট
[1,-2,1] 5
আউটপুট
2
