Tổng mảng con tối đa trong một phạm vi nhất định trong C ++

Chúng tôi được cung cấp với một mảng các phần tử số nguyên có kích thước bất kỳ. Nhiệm vụ là tìm tổng lớn nhất sẽ được tính bằng cách tạo các mảng con từ mảng đã cho trong phạm vi đã cho, có thể được bắt đầu từ bất kỳ giá trị chỉ mục nào có thể trong một mảng.

Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -

Trong - int arr [] ={3, 2, -1, 6, 7, 2}, int first =0, int last =5

Hết - Tổng mảng con tối đa trong một Phạm vi nhất định là:19

Giải thích - chúng tôi được cung cấp với một mảng chứa cả giá trị âm và dương và một phạm vi bắt đầu từ 0 đến 5, tức là bao gồm tất cả các chỉ mục của một mảng. Vì vậy, mảng con với tổng tối đa có thể là 3 + 6 + 7 + 2 + 2 - 1, tức là 19.

Trong - int arr [] ={-2, 1, 3, 4, 8, 9, 23}, int first =0, int last =3

Hết - Tổng mảng con tối đa trong một Phạm vi nhất định là:8

Giải thích - chúng tôi được cung cấp với một mảng chứa cả giá trị âm và dương và một phạm vi bắt đầu từ 0 đến 3, tức là bao gồm từ 0 đến 3 chỉ mục của một mảng. Vì vậy, mảng con với tổng tối đa có thể là 1 + 3 + 4, tức là 8.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Tạo cấu trúc cho cây sẽ lưu trữ max_val, max_temp, total, sub_sum dưới dạng các biến thành viên và đặt max_val, max_temp, sum_sum và total làm giá trị tối đa bằng cách sử dụng hàm tạo mặc định.
Tạo một phương thức cấu trúc dưới dạng set_node sẽ tạo thành cây bằng cách đặt max_val là max (left.max_val, left.total + right.max_val), max_temp là max (right.max_temp, right.total + left.max_temp), tổng là left.total + right.total và sub_sum là max ({left.sub_sum, right.sub_sum, left.max_temp + right.max_val}) rồi trả về nút.
Tạo một phương thức dưới dạng build_tree sẽ được sử dụng để tạo cây.
- Kiểm tra IF first =last, sau đó đặt tổng số, max_temp, max_val và sub_sum là arr [first] và trả về.
- Gọi phương thức build_tree dưới dạng build_tree (node, arr, first, temp, 2 * inx) và build_tree (node, arr, temp + 1, last, 2 * inx + 1) sau đó đặt node [inx] thành set_nodes ( nút [2 * inx], nút [2 * inx + 1])
Tạo một phương thức dưới dạng create_tree và đặt tạm thời là (int) (ceil (log2 (size))) sau đó thực hiện cuộc gọi đến phương thức build_tree () bằng cách chuyển đối tượng nút của cây, arr, giá trị 0, kích thước của mảng -1, giá trị 1 làm đối số.
Tạo một phương thức để tìm tổng của mảng con tối đa dưới dạng Maximum_sub (Nút cây *, int temp, int temp_2, int temp_3, int temp_4, int inx)
- Kiểm tra NẾU nhiệt độ lớn hơn temp_4 HOẶC temp_2 nhỏ hơn temp_3 sau đó trả về NULL
- Kiểm tra IF temp lớn hơn temp_3 VÀ temp_2 nhỏ hơn temp_4 rồi trả về nút [inx]
- Thực hiện lệnh gọi đến phương thức ở bên trái để gọi hàm Maximum_sub (nút, tạm thời, giữa, temp_3, temp_4, 2 * inx) và phải đến max_sub (nút, giữa + 1, temp_2, temp_3, temp_4, 2 * inx + 1 )
- Đặt kết quả là set_nodes (trái, phải)
- Trả về kết quả.
Tạo một phương thức dưới dạng Maximum_subarray (Tree * node, int first, int last, int size)
- Tạo một lệnh gọi phương thức dưới dạng Maximum_sub (node, 0, size - 1, first, last, 1)
- Trả về temp.sub_sum
Trong hàm main ()
- Khai báo một mảng các kiểu số nguyên với các giá trị âm và dương và tính kích thước của một mảng.
- Xác định phạm vi từ chỉ mục đầu tiên đến chỉ mục cuối cùng.
- Gọi hàm Maximum_subarray (nút, đầu tiên, cuối cùng, kích thước) để tính tổng của mảng con tối đa trong phạm vi đã cho

Ví dụ

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

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

Maximum Subarray Sum in a given Range is: 19