Di Jawa, cari jumlah subarray maksimum subarray selepas membahagikan tatasusunan kepada subarray berdasarkan pertanyaan yang diberikan

Kami mempunyai dua tatasusunan integer, satu dengan elemen yang dikira dan satu lagi dengan titik selisih yang diperlukan untuk memisahkan tatasusunan untuk menghasilkan subset, kami perlu mengira jumlah setiap subset dalam setiap pecahan dan mengembalikan subset maksimum

Mari kita fahami melalui contoh:-

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

Output− Jumlah sub-array maksimum [22, 13, 9, 9] selepas setiap pemisahan Jumlah subset

Selepas pemisahan pertama → {9} dan {4,5,6,7} >> Jumlah sub-baris maksimum ialah - 22

Selepas pemisahan kedua strong> → {9}, { 4,5 } dan {6,7} >> Jumlah sub-baris maksimum ialah - 13

Selepas pembahagian ketiga →{ 9}, {4,5}, {6} dan {7} >> Subarray maksimum Jumlah tatasusunan ialah - 9

Selepas pemisahan keempat →{9}, {4}, {5}, {6 } dan {7} >> Jumlah subarray maksimum ialah- 9

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

Output−Jumlah subarray maksimum selepas setiap pemisahan [15, 115, 10, 9]

Penjelasan−Di sini kita menguraikan tatasusunan mengikut titik pembahagiannya dan memperoleh subset maksimum selepas setiap pemisahan

Selepas pemisahan pertama → {7, 8} dan {5,9,1} >> Jumlah sub-array maksimum ialah 15

Selepas pemisahan kedua → {7,8}, {5} dan {9,1} >> Jumlah sub-tatasusunan maksimum ialah 15 115

Selepas bahagian ketiga →{7}, {8}, {5} dan {9,1} >> Maksimum jumlah sub-array ialah 10

Selepas pembahagian keempat →{7}, {8}, {5}, {9} dan {1} >> Jumlah sub-array maksimum ialah 9

Kaedah yang digunakan dalam atur cara berikut adalah seperti berikut-

Kami akan bermula dari kaedah utama()

• Tatasusunan input bagi sebarang panjang tertentu, seperti arr[] dan splitPoints[]. Panjangnya dikira dan dihantar kepada kaedah dalam bentuk calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr).

  Dalam kaedah calculateSubsetSum()

• buat tatasusunan integer sebagai sum[] dan tetapkan sum[0] kepada arr[0].

  • Mulakan gelung FOR daripada i ke 1 sehingga panjang tatasusunan, dan tetapkan jumlah[i] kepada jumlah[i - 1] + arr[i] dan tetapkan temp[0] kepada subSet baharu(0, n - 1, jumlah[n - 1]).

  • Teruskan menambah t2.add(temp[0]) dan t1.add(0)

  • Mulakan gelung FOR dari i ke 0 sehingga panjang tatasusunan splitPoints. Di dalam gelung tetapkan CurrentSplitPoint kepada t1.floor(splitPoints[i]) dan alih keluar dari t2 ke t2.remove(temp[currentSplitPoint])

  • set end to temp[currentSplitPoint] .last and temp[currentSplitPoint] as new subSets (currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]))

  • gunakan t2.add(temp[splitSplitPoint]litPoint]) dan templat [i] + 1] = subSet baharu(splitPoints[i] + 1, end, sum[end] - sum[splitPoints[i] add]])

  • guna t2.add(temp[splitPoints [i] + 1]), t1.add(currentSplitPoint) dan t1.add(splitPoints[i] + untuk menambah 1)

  • cetak nilai t2.first().

  Buat subSet kelas dan isytiharkan pertama, terakhir dan nilai sebagai ahli datanya dan tentukan pembina lalai sebagai subSet(int f, int l, int v) dan tetapkan dahulu kepada f, terakhir Set kepada l dan nilai untuk v

• Buat kelas sebagai utilitiComparator yang akan melaksanakan Comparator

• Buat kaedah awam sebagai perbandingan dan semak jika s2.value tidak sama dengan s1.value dan kemudian kembalikan s2.value - s1.

  • Semak sama ada s1.first tidak sama dengan s2.first dan kembalikan s2.first - s1.first

  • p>

  Contoh

  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 di atas

Jika kita akan menjalankan kod berikut di atas

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

Atas ialah kandungan terperinci Di Jawa, cari jumlah subarray maksimum subarray selepas membahagikan tatasusunan kepada subarray berdasarkan pertanyaan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!