ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม k งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของอาร์เรย์ย่อยสูงสุดในอาร์เรย์ที่สร้างขึ้นหลังจากการต่อกันซ้ำๆ
คำอธิบายปัญหา − เราจะหาผลรวมสูงสุดของ subarray ที่นำมาจากอาร์เรย์ที่สร้างขึ้นหลังจาก 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
วิธีนี้เป็นวิธีที่ดีแต่เป็นวิธีที่มีประสิทธิภาพมากกว่าในการแก้ปัญหานั้นสามารถทำได้โดยใช้เลขคณิตแบบแยกส่วน
เลขคณิตแบบแยกส่วน คือเวลาที่เราใช้ตัวดำเนินการโมดูโลเพื่อหาส่วนที่เหลือของสมการ
ในการแก้ปัญหา เราจะใช้เลขคณิตแบบแยกส่วนแทนการสร้าง thearray โดยการต่อกันซ้ำๆ วิธีการพักผ่อนยังคงเหมือนเดิม
ตัวอย่าง
โปรแกรมเพื่ออธิบายการทำงานของโซลูชันของเรา
#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
