Chúng ta được cung cấp hai mảng số nguyên, một mảng có các phần tử được tính toán và một mảng có các điểm phân tách được yêu cầu để tách mảng để tạo tập hợp con và chúng ta phải tính tổng của mỗi tập hợp con trong mỗi lần chia và trả về tổng tập hợp con tối đa.
Hãy cho chúng tôi hiểu với ví dụ:-
Đầu vào - int arr [] =int arr [] ={9, 4, 5, 6, 7} int splitPoints [] ={0, 2, 3, 1};
Đầu ra - Tổng mảng con tối đa sau mỗi lần tách [22, 13, 9, 9]
Giải thích - Ở đây chúng ta sẽ chia mảng theo các điểm phân tách của chúng và thu được tổng tập hợp con tối đa sau mỗi lần tách
Sau lần chia đầu tiên → {9} và {4,5,6,7}>> Tổng mảng con tối đa là- 22
Sau lần chia thứ hai → {9}, {4,5} và {6,7}>> Tổng mảng con tối đa là- 13
Sau phần chia thứ ba → {9}, {4,5}, {6} và {7}>> Tổng mảng con tối đa là- 9
Sau lần chia tay thứ tư → {9}, {4}, {5}, {6} và {7}>> Tổng mảng con tối đa là- 9
Đầu vào −int arr [] =int arr [] ={7, 8, 5, 9, 1} int splitPoints [] ={1, 2, 0, 3};
Đầu ra −Tổng số mảng con tối đa sau mỗi lần tách [15, 115, 10, 9]
Giải thích − Ở đây chúng ta đang chia mảng theo các điểm phân tách của chúng và nhận được tổng tập hợp con tối đa sau mỗi lần tách
Sau lần chia đầu tiên → {7,8} và {5,9,1}>> Tổng mảng con tối đa là 15
Sau lần chia thứ hai → {7,8}, {5} và {9,1}>> Tổng mảng con tối đa là 115
Sau phần chia thứ ba → {7}, {8}, {5} và {9,1}>> Tổng mảng con tối đa là 10
Sau lần chia tay thứ tư → {7}, {8}, {5}, {9} và {1}>> Tổng mảng con tối đa là 9
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
-
Chúng ta sẽ bắt đầu với phương thức main ()
-
Các mảng đầu vào có độ dài nhất định bất kỳ, giả sử arr [] và splitPoints []. Tính toán độ dài của chúng và chuyển đến phương thức dưới dạng allowSubsetSum (arr.length, splitPoints.length, splitPoints, arr).
-
-
Bên trong phương thức allowSubsetSum ()
-
Tạo một mảng số nguyên dưới dạng sum [] và đặt sum [0] là arr [0].
-
Bắt đầu vòng lặp FOR từ i đến 1 cho đến độ dài của một mảng và đặt sum [i] thành sum [i - 1] + arr [i] và đặt tạm thời [0] thành các Tập con mới (0, n - 1, sum [n - 1]).
-
Tiếp tục thêm t2.add (temp [0]) và t1.add (0)
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến độ dài của mảng splitPoints. Bên trong vòng lặp, đặt currentSplitPoint thành t1.floor (splitPoints [i]) và xóa khỏi t2 dưới dạng t2.remove (temp [currentSplitPoint])
-
Đặt kết thúc là temp [currentSplitPoint] .last và tạm thời [currentSplitPoint] dưới dạng các tập con mới (currentSplitPoint, splitPoints [i], sum [splitPoints [i]] - (currentSplitPoint ==0? 0:sum [currentSplitPoint - 1]))
-
Thêm bằng cách sử dụng t2.add (temp [currentSplitPoint]) và temp [splitPoints [i] + 1] =new subSets (splitPoints [i] + 1, end, sum [end] - sum [splitPoints [i]])
-
Thêm bằng cách sử dụng t2.add (temp [splitPoints [i] + 1]), t1.add (currentSplitPoint) và t1.add (splitPoints [i] + 1)
-
In giá trị t2.first ().
-
-
Tạo một lớp dưới dạng Tập hợp con của lớp và khai báo giá trị đầu tiên, cuối cùng và giá trị làm thành viên dữ liệu của nó và xác định phương thức khởi tạo mặc định là Tập hợp con (int f, int l, int v) và đặt đầu tiên thành f, cuối cùng thành l và giá trị thành v
-
Tạo một lớp dưới dạng tiện íchComparator sẽ IMPLEMENTS Comparator
-
Tạo một phương thức công khai như so sánh và kiểm tra IF s2.value không bằng s1.value rồi trả về s2.value - s1.value.
-
Kiểm tra IF s1.first không bằng s2.first rồi trả về s2.first - s1.first
-
Ví dụ
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
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Maximum subarray sum after each split 49 49 49 49 44 34