C++ में K-संयोजन अधिकतम योग

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

उदाहरण (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