ผลรวมของอาร์เรย์ย่อยสูงสุดหลังจากแบ่งอาร์เรย์ออกเป็นอาร์เรย์ย่อยตามการสืบค้นที่กำหนดใน Java

เราได้รับอาร์เรย์จำนวนเต็มสองชุด อันหนึ่งมีองค์ประกอบที่คำนวณได้ และอีกชุดหนึ่งมีจุดแยกซึ่งจำเป็นต้องแยกอาร์เรย์เพื่อสร้างชุดย่อย และเราต้องคำนวณผลรวมของชุดย่อยแต่ละชุดในทุกส่วนแยกและคืนค่าผลรวมชุดย่อยสูงสุด

ให้เราเข้าใจด้วยตัวอย่าง:-

ป้อนข้อมูล − int arr[] =int arr[] ={ 9, 4, 5, 6, 7 } int splitPoints[] ={ 0, 2, 3, 1 };

ผลผลิต − ผลรวมของ subarray สูงสุดหลังการแยกย่อยแต่ละครั้ง [22, 13, 9, 9]

คำอธิบาย - ที่นี่เรากำลังทำลายอาร์เรย์ตามจุดแยกและรับผลรวมย่อยสูงสุดหลังจากการแยกแต่ละครั้ง

หลังจากแยกครั้งแรก → {9} และ {4,5,6,7}>> ผลรวมของ subarray สูงสุดคือ- 22

หลังจากแยกที่สอง → {9}, {4,5} และ {6,7}>> ผลรวมของ subarray สูงสุดคือ- 13

หลังจากแยกสาม →{9}, {4,5}, {6} และ {7}>> ผลรวมของ subarray สูงสุดคือ- 9

หลังจากแยกที่สี่ →{9}, {4}, {5}, {6} และ {7}>> ผลรวมของ subarray สูงสุดคือ- 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}>> ผลรวมของ subarray สูงสุดคือ 15

หลังจากแยกที่สอง → {7,8}, {5} และ {9,1}>> ผลรวมของ subarray สูงสุดคือ 115

หลังจากแยกสาม →{7}, {8}, {5} และ {9,1}>> ผลรวมของ subarray สูงสุดคือ 10

หลังจากแยกที่สี่ →{7}, {8}, {5}, {9} และ {1}>> ผลรวมของ subarray สูงสุดคือ 9

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• เริ่มด้วย main() method

  • อาร์เรย์อินพุตของความยาวที่กำหนด เช่น arr[] และ splitPoints[] คำนวณความยาวและส่งผ่านไปยังเมธอดเป็น calcSubsetSum(arr.length, splitPoints.length, splitPoints, arr)

• ภายในเมธอด calSubsetSum()

  • สร้างอาร์เรย์จำนวนเต็มเป็น sum[] และตั้งค่า sum[0] เป็น arr[0]

  • เริ่มวนรอบ FOR จาก i ถึง 1 จนถึงความยาวของอาร์เรย์และตั้งค่า sum[i] เป็น sum[i - 1] + arr[i] และตั้งค่า temp[0] เป็นชุดย่อยใหม่ (0, n - 1, sum[n - 1]).

  • เพิ่ม t2.add(temp[0]) และ t1.add(0)

    . ต่อไป

  • เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงความยาวของอาร์เรย์ splitPoints ภายในลูปตั้งค่า 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] =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()

• สร้างคลาสเป็นชุดย่อยของคลาส และประกาศ first,last และ value เป็นสมาชิกข้อมูลและกำหนดคอนสตรัคเตอร์เริ่มต้นเป็น subSets (int f, int l, int v) และตั้งค่าเป็น f ก่อน สุดท้ายเป็น l และให้ค่าเป็น v

• สร้างคลาสเป็น utilityComparator ที่จะ IMPLEMENTS Comparator

  • สร้างวิธีการสาธารณะเพื่อเปรียบเทียบและตรวจสอบ 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