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 になります。

解き方の考え方

この問題は、連結後の巨大な配列を実際に構築しなくても、元の配列から次の 4 つの値を計算するだけで解けます。

• カダネのアルゴリズムによる最大部分配列和（getKadane）

• 配列全体の合計（getSum）

• 先頭から始まる最大の累積和（接頭辞の最大値）（getPrefix）

• 末尾で終わる最大の累積和（接尾辞の最大値）（getSuffix）

それぞれのメソッドは次のように動作します。

• getKadane()：ret := -inf、sum := 0 で初期化し、i を 0 から配列サイズ - 1 まで順に処理します（各値は mod 10^9 + 7 で管理）。

  • sum := max(arr[i], arr[i] + sum)

  • ret := max(ret, sum)

  最後に、ret が負であれば 0 を、そうでなければ ret を返します。

• getSum()：ret := 0 とし、配列の全要素を順に加算して返します。

• getPrefix()：先頭から累積和を取りながら、その最大値を記録します。結果が負なら 0 を返します。

• getSuffix()：末尾から累積和を取りながら、その最大値を記録します。結果が負なら 0 を返します。

メインの処理では、これらの値を組み合わせて次のように答えを決定します。

• 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 ) を返す

sum が正のときは、中央に挟まれる (k − 2) 個分のコピーを丸ごと含めるのが得であり、その両端に prefix と suffix を付け加えることで最大値が得られます。sum が正でない場合は、最初と最後のコピーだけをつなげた範囲（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