Tổng lớn nhất của mảng con sau khi chia mảng dựa trên các truy vấn cho trước trong Java

Chúng ta được cho hai mảng nguyên: một chứa các phần tử cần tính toán và một chứa các điểm chia để tách mảng thành các tập con. Nhiệm vụ là tính tổng của mỗi tập con sau mỗi lần chia và trả về tổng tập con lớn nhất.

Ví dụ minh họa

Đầu vào: int arr[] = { 9, 4, 5, 6, 7 }, int splitPoints[] = { 0, 2, 3, 1 };

Đầu ra: Tổng lớn nhất của mảng con sau mỗi lần chia [22, 13, 9, 9]

Giải thích: Chia mảng theo các điểm chia và lấy tổng lớn nhất sau mỗi lần chia.

Sau lần chia thứ nhất: {9} và {4,5,6,7} → Tổng lớn nhất: 22
Sau lần chia thứ hai: {9}, {4,5} và {6,7} → Tổng lớn nhất: 13
Sau lần chia thứ ba: {9}, {4,5}, {6} và {7} → Tổng lớn nhất: 9
Sau lần chia thứ tư: {9}, {4}, {5}, {6} và {7} → Tổng lớn nhất: 9

Đầu vào: int arr[] = { 7, 8, 5, 9, 1 }, int splitPoints[] = { 1, 2, 0, 3 };

Đầu ra: Tổng lớn nhất của mảng con sau mỗi lần chia [15, 115, 10, 9]

Giải thích:

Lần chia 1: {7,8} và {5,9,1} → Tổng lớn nhất: 15
Lần chia 2: {7,8}, {5} và {9,1} → Tổng lớn nhất: 115
Lần chia 3: {7}, {8}, {5} và {9,1} → Tổng lớn nhất: 10
Lần chia 4: {7}, {8}, {5}, {9} và {1} → Tổng lớn nhất: 9

Phương pháp tiếp cận

Bắt đầu từ phương thức main()
Truyền mảng đầu vào arr[] và splitPoints[] cùng độ dài vào phương thức calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr)
Trong calculateSubsetSum():
- Tạo mảng sum[] với sum[0] = arr[0]
- Vòng lặp từ i=1 đến n-1: sum[i] = sum[i-1] + arr[i]
- Khởi tạo temp[0] = new subSets(0, n-1, sum[n-1])
- Sử dụng TreeSet t1 (lưu chỉ số) và t2 (lưu subSets với comparator tùy chỉnh)
- Duyệt qua các điểm chia, cập nhật các tập con và lấy giá trị lớn nhất từ t2.first()
Lớp subSets chứa first, last, value
Lớp utilityComparator implements Comparator<subSets> so sánh theo value giảm dần, sau đó first giảm dần

Ví dụ mã Java

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

class utilityComparator implements Comparator<subSets> {
    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;
    int last;
    int 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<Integer> t1 = new TreeSet<>();
        TreeSet<subSets> 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);
    }
}

Đầu ra

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