ผลรวมเซิร์ฟอาร์เรย์สูงสุดในอาร์เรย์ที่สร้างหลังการต่อซ้ำในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม k ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมเซิร์ฟอาร์เรย์สูงสุดในอาร์เรย์ที่สร้างหลังการต่อซ้ำ

คำอธิบายปัญหา

เราจะหาผลรวมสูงสุดของเซิร์ฟอาร์เรย์ที่หยิบมาจากอาร์เรย์ที่สร้างขึ้นหลังจากทำซ้ำ arr จำนวน k ครั้ง

ตัวอย่าง

อินพุต

arr[] = {-9, -5, 14, 6} 
k = 2

เอาต์พุต

26

คำอธิบาย

อาร์เรย์ใหม่หลังทำซ้ำ: {-9, -5, 14, 6, -9, -5, 14, 6} 
เซิร์ฟอาร์เรย์ที่มีผลรวมสูงสุด = {14, 6, -9, -5, 14, 6} 
ผลรวม = 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

แนวทางนี้ดีแต่อยู่ แต่มีวิธีแก้ที่มีประสิทธิภาพมากกว่าที่เป็นไปได้โดยใช้คณิตศาสตร์แบบโมดุลาร์

คณิตศาสตร์แบบโมดุลาร์ (Modular Arithmetic) คือการที่เราใช้ออปเปอเรเตอร์โมดุลโอเพื่อหาเศษของสมการ

ในการแก้ปัญหา เราจะใช้คณิตศาสตร์แบบโมดุลาร์แทนการสร้างอาร์เรย์โดยการต่อซ้ำ ส่วนที่เหลือของวิธีแก้ยังคงเหมือนเดิม

ตัวอย่างโค้ด (วิธีที่มีประสิทธิภาพมากกว่า)

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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