우리에게는 두 개의 정수 배열이 주어졌습니다. 하나는 계산된 요소가 있고 다른 하나는 부분 집합을 만들기 위해 배열을 분할하는 데 필요한 분할 지점이 있으며 모든 분할에서 각 부분 집합의 합계를 계산하고 최대 부분 집합 합계를 반환해야 합니다.
예를 들어 이해합시다:-
입력 - int arr[] =int arr[] ={ 9, 4, 5, 6, 7 } int splitPoints[] ={ 0, 2, 3, 1 };
출력 − 각 분할 후 최대 하위 배열 합계 [22, 13, 9, 9]
설명 − 여기에서 분할 지점에 따라 배열을 나누고 각 분할 후 최대 부분 집합 합계를 구합니다.
첫 번째 분할 후 → {9} 및 {4,5,6,7}>> 최대 하위 배열 합계는 22
두 번째 분할 후 → {9}, {4,5} 및 {6,7}>> 최대 하위 배열 합계는 13
세 번째 분할 후 →{9}, {4,5}, {6} 및 {7}>> 최대 하위 배열 합계는 9
네 번째 분할 이후 →{9}, {4}, {5}, {6} 및 {7}>> 최대 하위 배열 합계는 - 9
입력 -int arr[] =int arr[] ={ 7, 8, 5, 9, 1 } int splitPoints[] ={ 1, 2, 0, 3 };
출력 −각 분할 후 최대 하위 배열 합계 [15, 115, 10, 9]
설명 −여기서 분할점에 따라 배열을 나누고 각 분할 후 최대 부분집합 합계를 구합니다.
첫 번째 분할 후 → {7,8} 및 {5,9,1}>> 최대 하위 배열 합계는 15입니다.
두 번째 분할 후 → {7,8}, {5} 및 {9,1}>> 최대 하위 배열 합계는 115입니다.
세 번째 분할 후 →{7}, {8}, {5} 및 {9,1}>> 최대 하위 배열 합계는 10입니다.
네 번째 분할 이후 →{7}, {8}, {5}, {9} 및 {1}>> 최대 하위 배열 합계는 9입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -
-
main() 메소드부터 시작하겠습니다.
-
주어진 길이의 입력 배열, 예를 들어 arr[] 및 splitPoints[]. 길이를 계산하고 메서드에 computeSubsetSum(arr.length, splitPoints.length, splitPoints, arr)으로 전달합니다.
-
-
computeSubsetSum()
메소드 내부-
정수 배열을 sum[]으로 만들고 sum[0]을 arr[0]으로 설정합니다.
-
루프 FOR를 i에서 1까지 배열의 길이까지 시작하고 sum[i]를 sum[i - 1] + arr[i]로 설정하고 temp[0]을 new subSets(0, n - 1, sum[n -)로 설정합니다. 1]).
-
계속 t2.add(temp[0]) 및 t1.add(0)
추가 -
splitPoints 배열의 길이까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 currentSplitPoint를 t1.floor(splitPoints[i])로 설정하고 t2에서 t2.remove(temp[currentSplitPoint])
로 제거합니다. -
끝을 temp[currentSplitPoint].last로 설정하고 temp[currentSplitPoint]를 new subSets(currentSplitPoint, splitPoints[i], sum[splitPoints[i]]] - (currentSplitPoint ==0 ? 0 :sum[currentSplitPoint - 1]))<로 설정합니다. /P>
-
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)
를 사용하여 추가 -
t2.first() 값을 출력합니다.
-
-
클래스를 subSets로 만들고 first, last 및 value를 데이터 멤버로 선언하고 기본 생성자를 subSets(int f, int l, int v)로 정의하고 first를 f로, last를 l로, value를 v
로 설정합니다. -
Comparator
를 구현하는 utilityComparator로 클래스를 만듭니다.-
비교로 공개 메소드를 생성하고 IF s2.value가 s1.value와 같지 않은지 확인한 다음 s2.value - s1.value를 반환합니다.
-
s1.first가 s2.first와 같지 않은지 확인한 다음 s2.first - s1.first를 반환합니다.
-
예
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);
}
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Maximum subarray sum after each split 49 49 49 49 44 34