ผลรวมสูงสุดของอาร์เรย์ซ้ำ K ครั้งใน C++

ให้อาร์เรย์ arr และจำนวนเต็ม k สร้างอาร์เรย์ใหม่โดยการซ้ำ arr จำนวน k ครั้ง (เช่น arr=[1,2], k=3 → [1,2,1,2,1,2]) ต้องการหาผลรวมสูงสุดของย่อยอาร์เรย์ (subarray) ในอาร์เรย์ใหม่นี้ คำตอบ modulo 10^9+7 ย่อยอาร์เรย์อาจว่างได้ (ผลรวม 0)

ตัวอย่าง: arr=[1,-2,1], k=5 → 2

ขั้นตอนการแก้ปัญหา

1. คำนวณ 4 ค่าสำคัญของ arr เดียว:
   • kadane = ผลรวมสูงสุดของย่อยอาร์เรย์ (Kadane's algorithm)
   • sum = ผลรวมทั้งอาร์เรย์
   • prefix = ผลรวมคำนำหน้าสูงสุด
   • suffix = ผลรวมคำต่อท้ายสูงสุด
2. ถ้า k == 1 คืน kadane
3. ถ้า 0: คำตอบ = max((sum * (k-2)) + prefix + suffix, kadane)
4. ถ้า sum <= 0: คำตอบ = max(prefix + suffix, kadane)

เหตุผล: ถ้าผลรวมทั้งอาร์เรย์บวก จะนำอาร์เรย์กลางมาใช้ซ้ำได้หลายครั้ง

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

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int MOD = 1e9 + 7;

int add(lli a, lli b) { return ((a % MOD) + (b % MOD)) % MOD; }
int mul(lli a, lli b) { return ((a % MOD) * (b % MOD)) % MOD; }

class Solution {
public:
    int getKadane(vector<int>& arr) {
        int ret = INT_MIN, sum = 0;
        for (int x : arr) {
            sum = max(x, x + sum);
            ret = max(ret, sum);
            sum %= MOD; ret %= MOD;
        }
        return ret < 0 ? 0 : ret;
    }
    int getSum(vector<int>& arr) {
        int ret = 0;
        for (int x : arr) { ret += x; ret %= MOD; }
        return ret;
    }
    int getPrefix(vector<int>& arr) {
        int ret = INT_MIN, sum = 0;
        for (int x : arr) {
            sum += x; sum %= MOD;
            ret = max(ret, sum); ret %= MOD;
        }
        return ret < 0 ? 0 : ret;
    }
    int getSuffix(vector<int>& arr) {
        int ret = INT_MIN, sum = 0;
        for (int i = arr.size()-1; i >= 0; i--) {
            sum += arr[i]; sum %= MOD;
            ret = max(ret, sum); ret %= MOD;
        }
        return ret < 0 ? 0 : ret;
    }
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int kadane = getKadane(arr);
        int sum = getSum(arr);
        int prefix = getPrefix(arr);
        int suffix = getSuffix(arr);
        if (k == 1) return kadane;
        if (sum > 0) {
            return max(add(mul(k-2, sum), add(prefix, suffix)), kadane);
        } else {
            return max(add(prefix, suffix), kadane);
        }
    }
};

int main() {
    vector<int> v1 = {1,-2,1};
    Solution ob;
    cout << ob.kConcatenationMaxSum(v1, 5);
}

Input

[1,-2,1] 5

Output

2