একটি পূর্ণসংখ্যা অ্যারে arr আর একটি পূর্ণসংখ্যা k দেওয়া আছে। অ্যারেটিকে k বার রিপিট করে পরিবর্তিত অ্যারে বানাতে হবে। যেমন, arr = [1, 2], k = 3 হলে পরিবর্তিত অ্যারে: [1, 2, 1, 2, 1, 2]। এখন এই পরিবর্তিত অ্যারেতে সর্বোচ্চ উপ-অ্যারে যোগফল বের করতে হবে। উপ-অ্যারের দৈর্ঘ্য ০ হতে পারে (সেক্ষেত্রে যোগফল ০)। ফলাফল বড় হতে পারে, তাই 10^9 + 7 দিয়ে মডুলো নিয়ে ফেরত দিন। উদাহরণ: [1,-2,1], k = 5 হলে ফলাফল ২।
সমাধানের ধাপগুলো:
getKadane()মেথড বানান যা অ্যারে নেবে:ret := -inf, sum := 0(সব মড10^9+7)i = 0থেকেarr.size()-1পর্যন্ত:sum := max(arr[i], arr[i] + sum)ret := max(ret, sum)
ret < 0হলে ০ ফেরত দিন, অন্যথায়ret।
getSum()মেথড: অ্যারেটির সব উপাদানের যোগফল (মড10^9+7)।getPrefix()মেথড: প্রিফিক্স সর্বোচ্চ যোগফল (মড10^9+7)।getSuffix()মেথড: সাফিক্স সর্বোচ্চ যোগফল (মড10^9+7)।- মূল মেথড:
kadane := getKadane(arr), sum := getSum(arr), prefix := getPrefix(arr), suffix := getSuffix(arr)- যদি
k == 1,kadaneফেরত দিন। - যদি
sum > 0,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
