मान लीजिए कि हमारे पास एक पूर्णांक सरणी गिरफ्तारी और एक पूर्णांक k है, हमें सरणी को 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 के सभी मान मॉड 10^9 + 7
के होंगे -
मेरे लिए 0 से लेकर एआर के आकार तक - 1
-
योग :=अधिकतम गिरफ्तारी [i] और गिरफ्तारी [i] + राशि
-
रिट :=अधिकतम रिट, योग
-
-
अगर रिट <0 है, तो 0 लौटाएं, अन्यथा रिटायर करें
-
GetSum () नामक विधि को परिभाषित करें, यह सरणी लेगा, यह काम करेगा -
-
ret :=0, ret value mod 10^9 + 7
. का होगा -
मेरे लिए 0 से लेकर एआर के आकार तक - 1
-
रिट :=रिट + एआर [i]
-
-
वापसी रिट
-
GetPrefix() नामक विधि को परिभाषित करें, यह सरणी लेगा, यह इस तरह काम करेगा -
-
ret :=-inf, sum :=0, ret और sum के सभी मान मॉड 10^9 + 7
के होंगे -
मेरे लिए 0 से लेकर एआर के आकार तक - 1
-
योग:=योग + गिरफ्तारी [i]
-
रिट :=अधिकतम रिट और योग
-
-
अगर रिट <0 है, तो 0 लौटाएं, अन्यथा रिटायर करें
-
GetSuffix() नामक विधि को परिभाषित करें, यह सरणी लेगा, यह काम करेगा -
-
ret :=inf, sum :=0, ret और sum के सभी मान mod 10^9 + 7
के होंगे -
मेरे लिए एआर के रेंज आकार में - 1 से 0 तक
-
योग:=योग + गिरफ्तारी [i]
-
रिट :=अधिकतम रिट और योग
-
-
अगर रिट <0 है, तो 0 लौटाएं, अन्यथा रिटायर करें
-
मुख्य विधि से, निम्न कार्य करें -
-
kadane:=getKadane(arr), sum:=getSum(arr), उपसर्ग:=getPrefix(arr), प्रत्यय:=getSuffix(arr)
-
अगर k 1 है, तो kadane वापस करें
-
अगर योग> 1, तो अधिकतम (योग * (के - 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