C++で指定された配列をk回繰り返すことによって形成された配列の最大サブ配列合計

この問題では、配列と数kが与えられます。私たちのタスクは、c++で指定された配列をk回繰り返すことによって形成された配列の最大サブ配列合計を見つけるプログラムを作成することです。

問題の説明 −ここでは、指定された配列をk回繰り返して形成された配列から形成されたサブ配列の最大合計を求めます。

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

入力 −配列={3、5、1} k =2

出力 − 18

説明 −

array formed by repeating k times,
array = {3, 5, 1, 3, 5, 1}
Maximum subarray sum = 3+5+1+3+5+1 = 18

この問題を解決するために、配列のすべての要素の合計を計算します。

次に、合計に基づいて、サブアレイの合計計算を計算します。

合計が0より大きい場合、実際の合計を与えた配列の合計をk倍します。

sum <0の場合、maxSumが2回の配列の繰り返しを行うサブ配列が見つかります。

例

ソリューションの実装を示すプログラム

#include<iostream>
using namespace std;
void repeatArray(int *arr, int *b, int k,int len) {
   int j = 0;
   while (k > 0){
      for (int i = 0; i < len; i++)
      b[j++] = arr[i];
      k--;
   }
}
long subArraySum(int *a,int len) {
   int max = 0;
   long newmax = 0;
   for (int i = 0; i < len; i++) {
      newmax = newmax + a[i];
   if (max < newmax)
      max = newmax;
   if (newmax < 0)
      newmax = 0;
   }
   return max;
}
long findMaxSubArraySum(int *arr, int k,int len) {
   int arraySum = 0;
   long maxSum = 0;
   int b[(2 * len)]= {0};
   repeatArray(arr, b, 2,len);
   for (int i = 0; i < len; i++)
   arraySum += arr[i];
   maxSum = subArraySum(b,2*len);
   if (arraySum > 0)
      maxSum = subArraySum(b,2*len) + (k - 2) * arraySum;
   return maxSum;
}
int main() {
   int arr[] = { 3, 5, 1};
   int length=sizeof(arr)/sizeof(arr[0]);
   int k = 3;
   cout<<"The maximum subarray sum in array formed by repeating the given array "<<k<<" times is "<<findMaxSubArraySum(arr, k,length);
   return 0;
}

出力

The maximum subarray sum in array formed by repeating the given array 3 times is 27