C++でのK-連結の最大合計

整数配列arrと1つの整数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のすべての値はmod 10 ^ 9+7になります

• 0からarrのサイズまでの範囲のiの場合– 1

  • 合計：=arr[i]およびarr[i]+合計の最大値

  • ret：=retの最大値、合計

• retが<0の場合は0を返し、そうでない場合はret

• getSum（）というメソッドを定義します。これは配列を取ります。これは-

  のように機能します。

• ret：=0、ret値はmod 10 ^ 9+7になります

• 0からarrのサイズまでの範囲のiの場合– 1

  • ret：=ret + arr [i]

• retを返す

• getPrefix（）というメソッドを定義します。これは配列を取ります。これは-

  のように機能します。

• ret：=-inf、sum：=0、retとsumのすべての値はmod 10 ^ 9+7になります

• 0からarrのサイズまでの範囲のiの場合– 1

  • 合計：=合計+ arr [i]

  • ret：=retと合計の最大値

• retが<0の場合は0を返し、そうでない場合はret

• getSuffix（）というメソッドを定義します。これは配列を取ります。これは-

  のように機能します。

• ret：=inf、sum：=0、retとsumのすべての値はmod 10 ^ 9+7になります

• arrの範囲サイズのiの場合–1から0まで

  • 合計：=合計+ arr [i]

  • ret：=retと合計の最大値

• retが<0の場合は0を返し、そうでない場合はret

• メインの方法から、次のようにします-

• kadane：=getKadane（arr）、sum：=getSum（arr）、prefix：=getPrefix（arr）、suffix：=getSuffix（arr）

• kが1の場合、kadaneを返します

• sum> 1の場合、（sum *（k-2））+プレフィックス+サフィックスとカダネの最大値を返します

• それ以外の場合は、（プレフィックス+サフィックス）と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