Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và một số nguyên k. Ourtask là tạo một chương trình để tìm tổng mảng con tối đa trong một mảng được tạo sau khi nối lặp lại.
Mô tả sự cố - Chúng ta sẽ tìm tổng lớn nhất của mảng con được lấy từ mảng được tạo sau khi lặp lại arr, k lần.
Ví dụ
Hãy lấy một ví dụ để hiểu vấn đề.
Đầu vào
arr[] = {−9, −5, 14, 6} k = 2 Đầu ra
26
Giải thích
New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản là tạo một mảng mới sẽ được hình thành sau khi nối arr [], k time, sau đó tìm mảng con có tổng lớn nhất.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum subarray sum in an array created after repeated concatenation is 26
Cách tiếp cận này là tốt nhưng có thể là một cách tiếp cận hiệu quả hơn để giải quyết vấn đề bằng cách sử dụng số học mô-đun.
Số học mô-đun là khi chúng ta sử dụng toán tử modulo để lấy phần còn lại của phương trình.
Để giải quyết vấn đề, chúng ta sẽ sử dụng số học mô-đun thay vì tạo mảng bằng cách nối lặp lại. Giải pháp còn lại vẫn như cũ.
Ví dụ
Chương trình minh họa giải pháp của chúng tôi đang hoạt động,
#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;
} Đầu ra
The maximum subarray sum in an array created after repeated concatenation is 26