Java에서는 주어진 쿼리를 기반으로 배열을 하위 배열로 분할한 후 하위 배열의 최대 하위 배열 합계를 찾습니다.

두 개의 정수 배열이 있습니다. 하나는 계산된 요소가 있고 다른 하나는 하위 집합을 생성하기 위해 배열을 분할하는 데 필요한 분할 점이 있습니다. 각 분할에서 각 하위 집합의 합을 계산하고 최대 하위 집합을 반환해야 합니다.

예를 들어 이해해 봅시다:-

Input− int arr[] = int arr[] = { 9, 4, 5, 6 , 7 } int SplitPoints[] = { 0, 2, 3, 1 } ;

Output− 각 분할 후 최대 하위 배열 합계 [22, 13, 9, 9] 하위 집합 합계

첫 번째 분할 후 → {9} 및 {4,5,6,7} >> 최대 하위 배열 합은 - 22

두 번째 분할 후 strong> → {9}, { 4,5 } 및 {6,7} >> 최대 하위 배열 합은 - 13

세 번째 분할 후 →{ 9}, {4,5}, {6} 및 {7} >> 최대 하위 배열 배열 합계는 - 9

4번째 분할 후 →{9}, {4}, {5}, {6 } 및 {7} >> 최대 하위 배열 합계는 9

Input−int arr[] = int arr[] = { 7, 8, 5, 9, 1 } int SplitPoints[] = { 1, 2 , 0, 3 };

Output−각 분할 후 최대 하위 배열 합계 [15, 115, 10, 9]

Explanation−여기서 분할 지점에 따라 배열을 분해하고 최대 하위 집합 합계를 얻습니다. 각 분할 후

첫 번째 분할 후 → {7, 8} 및 {5,9,1} >> 최대 하위 배열 합계는 15

두 번째 분할 후 → {7,8}, {5} 및 {9,1} >> 최대 하위 배열 합은 15 115

세 번째 나누기 이후 →{7}, {8}, {5} 및 {9,1} >> 최대 하위 배열 합은 10

네 번째 나누기 이후 →{7}, {8}, {5}, {9} 및 {1} >> 최대 하위 배열 합은 9

에서 사용되는 방법 다음 프로그램은 다음과 같습니다.

main() 메서드

• arr[] 및 SplitPoints[]와 같이 주어진 길이의 입력 배열부터 시작합니다. 해당 길이는 계산되어calculateSubsetSum(arr.length,splitPoints.length,splitPoints,arr) 형식으로 메서드에 전달됩니다.

  calculateSubsetSum()

• 메소드에서 정수 배열을 sum[]으로 만들고 sum[0]을 arr[0]으로 설정합니다.

  • 배열의 길이까지 i에서 1까지 FOR 반복을 시작하고 sum[i]를 sum[i - 1] + arr[i]로 설정하고 temp[0]을 new subSets(0, n - 1, 합계[n - 1]).

  • 계속해서 t2.add(temp[0]) 및 t1.add(0)

  • splitPoints 배열 길이까지 i에서 0까지 FOR 루프를 계속 추가하세요. 루프 내에서 currentSplitPoint를 t1.floor(splitPoints[i])로 설정하고 t2에서 t2.remove(temp[currentSplitPoint])

  • end를 temp[currentSplitPoint] .last로 설정하고 temp[currentSplitPoint]를 새 하위 집합으로 설정합니다. (currentSplitPoint, SplitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]))

  • t2.add(temp[currentSplitPoint]) 및 temp[splitPoints 사용 [i] + 1] = 새로운 하위 집합(splitPoints[i] + 1, end, sum[end] - sum[splitPoints[i] add]])

  • use 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로 설정 to v

• Comparator

• 를 구현할 유틸리티Comparator로 클래스를 만들고 s2.value가 s1.value와 같지 않은지 확인한 다음 s2 값을 반환합니다.

  • s1.first가 s2.first와 같지 않은지 확인하고 s2.first를 반환합니다. - s1.first

  • p>

  Example

  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);
     }
  }

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

르레

위 내용은 Java에서는 주어진 쿼리를 기반으로 배열을 하위 배열로 분할한 후 하위 배열의 최대 하위 배열 합계를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!