หาผลรวมย่อยสูงสุดหลังแบ่งอาร์เรย์ตามจุดแยกที่กำหนดใน Java

ภาพรวมปัญหา

ได้รับอาร์เรย์จำนวนเต็ม 2 อาร์เรย์: อาร์เรย์หนึ่งเก็บค่าที่ต้องคำนวณ อีกอาร์เรย์หนึ่งเก็บจุดแยก (split points) เพื่อแบ่งอาร์เรย์เป็นชุดย่อย (subsets) ต้องคำนวณผลรวมของแต่ละชุดย่อยในแต่ละครั้งที่แยก และคืนค่าผลรวมสูงสุดของชุดย่อยแต่ละขั้นตอน

ตัวอย่าง

ตัวอย่างที่ 1

Input: arr[] = { 9, 4, 5, 6, 7 }, splitPoints[] = { 0, 2, 3, 1 }

Output: Maximum subarray sum after each split [22, 13, 9, 9]

คำอธิบาย:

• แยกครั้งที่ 1: {9} และ {4,5,6,7} → ผลรวมสูงสุด = 22
• แยกครั้งที่ 2: {9}, {4,5} และ {6,7} → ผลรวมสูงสุด = 13
• แยกครั้งที่ 3: {9}, {4,5}, {6} และ {7} → ผลรวมสูงสุด = 9
• แยกครั้งที่ 4: {9}, {4}, {5}, {6} และ {7} → ผลรวมสูงสุด = 9

ตัวอย่างที่ 2

Input: arr[] = { 7, 8, 5, 9, 1 }, splitPoints[] = { 1, 2, 0, 3 }

Output: [15, 115, 10, 9]

แนวทางการแก้ปัญหา

• สร้างอาร์เรย์ prefix sum (sum[]) เพื่อคำนวณผลรวมช่วงได้ใน O(1)
• ใช้ TreeSet (t1) เก็บจุดเริ่มต้นของชุดย่อย และ TreeSet (t2) เก็บออบเจกต์ subSets เรียงตามค่าผลรวมมากไปน้อย
• เริ่มต้นมีชุดย่อยเดียวคือทั้งอาร์เรย์ (0 ถึง n-1)
• สำหรับแต่ละ split point:
  • หาชุดย่อยที่มีจุดเริ่มต้น ≤ split point (ใช้ t1.floor)
  • ลบชุดย่อยเดิมออกจาก t2
  • แบ่งชุดย่อยเดิมเป็น 2 ชุดย่อยใหม่: ส่วนซ้าย (currentSplitPoint ถึง splitPoint) และส่วนขวา (splitPoint+1 ถึง end)
  • คำนวณผลรวมแต่ละชุดย่อยจาก prefix sum และเพิ่มเข้า t2, t1
  • ค่าสูงสุดคือ t2.first().value

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

import java.util.*;

class utilityComparator implements Comparator {
    public int compare(subSets s1, subSets s2) {
        if (s2.value != s1.value) return s2.value - s1.value;
        if (s1.first != s2.first) return s2.first - s1.first;
        return 0;
    }
}

class subSets {
    int first, last, value;
    subSets(int f, int l, int v) { first = f; last = l; value = v; }
}

public class testClass {
    static void calculateSubsetSum(int n, int k, int splitPoints[], int arr[]) {
        int sum[] = new int[n];
        sum[0] = arr[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + arr[i];

        TreeSet t1 = new TreeSet<>();
        TreeSet t2 = new TreeSet<>(new utilityComparator());
        subSets temp[] = new subSets[n];
        temp[0] = new subSets(0, n - 1, sum[n - 1]);
        t2.add(temp[0]);
        t1.add(0);

        System.out.println("Maximum subarray sum after each split");
        for (int i = 0; i < k; i++) {
            int currentSplitPoint = t1.floor(splitPoints[i]);
            t2.remove(temp[currentSplitPoint]);
            int end = temp[currentSplitPoint].last;
            temp[currentSplitPoint] = new subSets(currentSplitPoint, splitPoints[i],
                sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]));
            t2.add(temp[currentSplitPoint]);
            temp[splitPoints[i] + 1] = new subSets(splitPoints[i] + 1, end,
                sum[end] - sum[splitPoints[i]]);
            t2.add(temp[splitPoints[i] + 1]);
            t1.add(currentSplitPoint);
            t1.add(splitPoints[i] + 1);
            System.out.println(t2.first().value);
        }
    }

    public static void main(String[] args) {
        int arr[] = { 2, 1, 6, 8, 5, 10, 21, 13 };
        int splitPoints[] = { 3, 1, 2, 0, 4, 5 };
        calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr);
    }
}

ผลลัพธ์

Maximum subarray sum after each split 49 49 49 49 44 34