C++プログラムで連結を繰り返した後に作成された配列の最大サブ配列合計

この問題では、サイズnと整数kの配列arr[]が与えられます。私たちのタスクは、連結を繰り返した後に作成された配列内の最大のサブ配列の合計を見つけるプログラムを作成することです。

問題の説明 −サブ配列の最大合計は、arrをk回繰り返した後に作成された配列から取得されます。

例

問題を理解するために例を見てみましょう。

入力

arr[] = {−9, −5, 14, 6} k = 2

出力

26

説明

New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26

ソリューションアプローチ

簡単な解決策は、arr []、k timeを連結した後に形成される新しい配列を作成し、合計が最大のサブ配列を見つけることです。このための最良の方法は、Kadaneのアルゴリズムを使用することです。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
   int newArr[2*n];
   for(int i = 0; i < k*n; i++)
   newArr[i] = arr[i%n];
   int maxSum = −1000, sum = 0;
   for (int i = 0; i < k*n; i++) {
      sum = sum + newArr[i];
      if (maxSum < sum)
         maxSum = sum;
      if (sum < 0)
         sum = 0;
   }
   return maxSum;
}
int main(){
   int arr[] = { −9, −5, 14, 6 };
   int k = 2;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum subarray sum in an array created after repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
   return 0;
}

出力

The maximum subarray sum in an array created after repeated
concatenation is 26

このアプローチは優れていますが、モジュラー演算を使用して問題を解決するためのより効率的なアプローチが可能です。

モジュラー演算 モジュロ演算子を使用して方程式の余りを取得する場合です。

この問題を解決するために、連結を繰り返して配列を作成する代わりに、モジュラー演算を使用します。残りのソリューションは同じままです。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
   int maxSum = −1000, sum = 0;
   for (int i = 0; i < k*n; i++) {
      sum = sum + arr[i%n];
      if (maxSum < sum)
         maxSum = sum;
      if (sum < 0)
         sum = 0;
   }
   return maxSum;
}
int main(){
   int arr[] = { −9, −5, 14, 6 };
   int k = 2;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum subarray sum in an array created after
   repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
   return 0;
}

出力

The maximum subarray sum in an array created after repeated
concatenation is 26