資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中給定範圍內的最大子陣列和
給定一個任意大小的整數陣列。任務是從給定陣列中在給定範圍內形成子陣列，計算最大和，子陣列可以從陣列中的任何可能的索引值開始。
讓我們看看各種輸入輸出場景：
輸入− int arr[] = { 3, 2, -1, 6, 7, 2 }, int first = 0, int last = 5
輸出− 給定範圍內的最大子陣列和為：19
解釋− 給定一個包含正數和負數的陣列，以及一個從0到5的範圍，即覆蓋陣列的所有索引。因此，最大和的子陣列可以是 3 + 6 + 7 + 2 + 2 - 1，即 19。
輸入− int arr[] = {-2, 1, 3, 4, 8, 9, 23}, int first = 0, int last = 3
輸出− 給定範圍內的最大子陣列和為：8
解釋− 給定一個包含正數和負數的陣列，以及一個從0到3的範圍，即覆蓋陣列的0到3索引。因此，最大和的子陣列可以是 1 + 3 + 4，即 8。
下面程式中使用的方法如下：
構建一個樹形結構，該結構將max_val、max_temp、total、sub_sum作為成員變數儲存，並使用預設建構函式將max_val、max_temp、sum_sum和total設定為最大值。
建立一個結構方法set_node，該方法將透過將max_val設定為max(left.max_val, left.total + right.max_val)，max_temp設定為max(right.max_temp, right.total + left.max_temp)，total設定為left.total + right.total，sub_sum設定為max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val})來構建樹，然後返回節點。
建立一個名為build_tree的方法，用於構建樹。
檢查IF first = last，然後將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(node[2 * inx], node[2 * inx + 1])
建立一個名為create_tree的方法，並將temp設定為(int)(ceil(log2(size)))，然後透過傳遞樹的node物件、arr、值0、陣列大小-1、值1作為引數來呼叫build_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，則返回NULL
檢查IF temp大於temp_3且temp_2小於temp_4，則返回node[inx]
呼叫方法，例如left呼叫函式maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx)和right呼叫maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1)
將result設定為set_nodes(left, right)
返回result。
建立一個名為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)來計算給定範圍內的最大子陣列和
示例
#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
251 次檢視
