ผลรวม Subarray สูงสุดในช่วงที่กำหนดใน C++

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

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน − int arr[] ={ 3, 2, -1, 6, 7, 2 }, int first =0, int สุดท้าย =5

ออก − ผลรวม Subarray สูงสุดในช่วงที่กำหนดคือ:19

คำอธิบาย − เราได้รับอาร์เรย์ที่มีทั้งค่าบวกและค่าลบและช่วงเริ่มต้นจาก 0 ถึง 5 นั่นคือครอบคลุมดัชนีทั้งหมดของอาร์เรย์ ดังนั้น subarray withmaximum sum สามารถเป็น 3 + 6 + 7 + 2 + 2 - 1 เช่น 19.

ใน − int arr[] ={-2, 1, 3, 4, 8, 9, 23}, int first =0, int สุดท้าย =3

ออก − ผลรวม Subarray สูงสุดในช่วงที่กำหนดคือ:8

คำอธิบาย − เราได้รับอาร์เรย์ที่มีทั้งค่าบวกและค่าลบและช่วงเริ่มต้นจาก 0 ถึง 3 นั่นคือครอบคลุม 0 ถึง 3 ดัชนีของอาร์เรย์ ดังนั้น subarray withmaximum sum สามารถเป็น 1 + 3 + 4 เช่น 8

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

• สร้างโครงสร้างสำหรับต้นไม้ที่จะเก็บ max_val, max_temp, total, sub_sum เป็นตัวแปรสมาชิก และตั้งค่า max_val, max_temp, sum_sum และผลรวมเป็นค่าสูงสุดโดยใช้ตัวสร้างเริ่มต้น

• สร้างเมธอดของโครงสร้างเป็น set_node ที่จะสร้างทรีโดยตั้งค่า max_val เป็น max(left.max_val, left.total + right.max_val), max_temp เป็น max(right.max_temp, right.total + left.max_temp) รวมเป็น left.total + right.total และ sub_sum เป็น max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val}) จากนั้นส่งคืนโหนด

• สร้าง method เป็น build_tree ที่จะใช้สร้าง tree

  • ตรวจสอบว่า IF first =last แล้ว set Total, max_temp, max_val และ sub_sum เป็น arr[first] และคืนค่า

  • เรียกใช้เมธอด build_tree ด้วย build_tree(node, arr, first, temp, 2 * inx) และ build_tree(node, arr, temp + 1, last, 2 * inx + 1) จากนั้นตั้งค่า node[inx] เป็น set_nodes( โหนด[2 * inx], โหนด[2 * inx + 1])

• สร้างเมธอดเป็น create_tree และตั้งค่า temp เป็น (int)(ceil(log2(size))) จากนั้นทำการเรียกเมธอด build_tree() โดยส่งโหนดอ็อบเจ็กต์ของ tree, arr, ค่า 0, ขนาดของอาร์เรย์ -1, ค่า 1 เป็นอาร์กิวเมนต์

• สร้างวิธีการเพื่อค้นหาผลรวมของ subarray สูงสุดเป็น maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx)

  • ตรวจสอบว่า temp มากกว่า temp_4 หรือ temp_2 น้อยกว่า temp_3 แล้วคืนค่า NULL

  • ตรวจสอบว่า temp มากกว่า temp_3 และ temp_2 น้อยกว่า temp_4 แล้วส่งคืน node[inx]

  • เรียกใช้เมธอดเป็นด้านซ้ายเพื่อเรียกใช้ฟังก์ชัน maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx) และ right to maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1 )

  • กำหนดผลลัพธ์เป็น set_nodes(ซ้าย, ขวา)

  • ส่งคืนผลลัพธ์

• สร้างวิธีการเป็น maximum_subarray(Tree* node, int first, int last, int size)

  • สร้างการเรียกเมธอดเป็น maximum_sub(node, 0, size - 1, first, last, 1)

  • ส่งคืน temp.sub_sum

• ในฟังก์ชัน main()

  • ประกาศอาร์เรย์ประเภทจำนวนเต็มที่มีค่าบวกและค่าลบ แล้วคำนวณขนาดของอาร์เรย์

  • กำหนดช่วงจากดัชนีแรกถึงดัชนีสุดท้าย

  • เรียกใช้ฟังก์ชัน maximum_subarray(node, first, last, size) เพื่อคำนวณผลรวมของ subarray สูงสุดในช่วงที่กำหนด

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
struct Tree{
   int max_val;
   int max_temp;
   int total;
   int sub_sum;
   Tree(){
      max_val = max_temp = sub_sum = -MAX;
      total = -MAX;
   }
};

Tree set_nodes(Tree left, Tree right){
   Tree node;
   node.max_val = max(left.max_val, left.total + right.max_val);
   node.max_temp = max(right.max_temp, right.total + left.max_temp);
   node.total = left.total + right.total;
   node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
   return node;
}
void build_tree(Tree* node, int arr[], int first, int last, int inx){
   if(first == last){
      node[inx].total = arr[first];
      node[inx].max_temp = arr[first];
      node[inx].max_val = arr[first];
      node[inx].sub_sum = arr[first];
      return;
   }
   int temp = (first + last) / 2;
   build_tree(node, arr, first, temp, 2 * inx);
   build_tree(node, arr, temp + 1, last, 2 * inx + 1);
   node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}
Tree* create_tree(int arr[], int size){
   int temp = (int)(ceil(log2(size)));
   int n = 2 * (int)pow(2, temp) - 1;
   Tree* node = new Tree[n];
   build_tree(node, arr, 0, size - 1, 1);
   return node;
}
Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx){
   if(temp > temp_4 || temp_2 < temp_3){
      Tree nullNode;
      return nullNode;
   }
   if(temp >= temp_3 && temp_2 <= temp_4){
      return node[inx];
   }
   int mid = (temp + temp_2) / 2;
   Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
   Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
   Tree result = set_nodes(left, right);
   return result;
}
int maximum_subarray(Tree* node, int first, int last, int size){
   Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
   return temp.sub_sum;
}
int main(){
   int arr[] = { 3, 2, -1, 6, 7, 2 };
   int size = sizeof(arr) / sizeof(arr[0]);
   Tree* node = create_tree(arr, size);
   int first = 0;
   int last = 5;
   int sub_sum = maximum_subarray(node, first, last, size);
   cout<< "Maximum Subarray Sum in a given Range is: "<< sub_sum;
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Maximum Subarray Sum in a given Range is: 19