이 문제에서는 크기가 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 시간을 연결한 후 형성될 새 배열을 만든 다음 최대 합을 갖는 하위 배열을 찾는 것입니다. 이를 위해 가장 좋은 방법은 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