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이 두 번 반복되는 배열을 사용하는 하위 배열을 찾습니다.

예시

솔루션 구현을 보여주는 프로그램,

#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