Trong bài toán này, chúng ta cho một mảng và một số k. Nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm tổng mảng con tối đa trong một mảng được tạo bằng cách lặp lại k thời gian cho mảng đã cho trong c ++.
Mô tả sự cố - Tại đây, chúng ta sẽ tìm tổng lớn nhất của mảng con được tạo thành từ mảng được tạo thành bằng cách lặp lại mảng đã cho k lần.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - mảng ={3, 5, 1} k =2
Đầu ra - 18
Giải thích -
array formed by repeating k times,
array = {3, 5, 1, 3, 5, 1}
Maximum subarray sum = 3+5+1+3+5+1 = 18 Để giải quyết vấn đề này, chúng ta sẽ tính tổng tất cả các phần tử của mảng.
Sau đó, dựa trên tổng, chúng tôi sẽ tính toán tổng của mảng con.
Nếu sum> 0, chúng ta sẽ nhân tổng của mảng k với tổng thực tế.
Nếu sum <0, chúng ta sẽ tìm thấy mảng con có maxSum nhận hai lần lặp lại mảng.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum subarray sum in array formed by repeating the given array 3 times is 27