ผลรวมเซิร์บอาร์เรย์สูงสุดของอาร์เรย์ที่ซ้ำ k ครั้งใน C++

โจทย์ปัญหา

ได้รับอาร์เรย์และตัวเลข k ให้สร้างอาร์เรย์ใหม่โดยการซ้ำอาร์เรย์เดิม k ครั้ง แล้วหาผลรวมเซิร์บอาร์เรย์สูงสุดของอาร์เรย์ใหม่นี้

ตัวอย่าง

นำเข้า: array = {3, 5, 1}, k = 2
สร้างอาร์เรย์: {3, 5, 1, 3, 5, 1}
ผลลัพธ์: 18 (3+5+1+3+5+1)

แนวคิดการแก้ปัญหา

1. คำนวณผลรวมทั้งหมดของอาร์เรย์เดิม (arraySum)
2. หาผลรวมเซิร์บอาร์เรย์สูงสุดของอาร์เรย์ที่ซ้ำ 2 ครั้ง (maxSum)
3. กรณีต่างๆ:
   • ถ้า arraySum > 0: ผลลัพธ์ = maxSum + (k - 2) * arraySum
   • ถ้า arraySum <= 0: ผลลัพธ์ = maxSum (ไม่ควรนำอาร์เรย์ทั้งหมดมารวม)

โค้ดตัวอย่าง (C++)

#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;
}

ผลลัพธ์

The maximum subarray sum in array formed by repeating the given array 3 times is 27

คำอธิบายเพิ่มเติม

ประเด็นสำคัญคือการจัดการกรณีที่ผลรวมอาร์เรย์เป็นบวก (ควรนำอาร์เรย์ทั้งก้อนมารวม) หรือเป็นลบ/ศูนย์ (ควรหาเฉพาะเซิร์บอาร์เรย์ที่ดีที่สุดใน 2 รอบแรก) ทำให้ประหยัดเวลาและหน่วยความจำได้มาก