C ++中给定范围内的最大子数组总和
我们得到了任何给定大小的整数元素数组。任务是找到将通过从给定范围内的给定数组形成子数组来计算的最大和，该子数组可以从数组中的任何可能的索引值开始。
让我们看看这个的各种输入输出场景-
In −intarr[]={3,2,-1,6,7,2},intfirst=0,intlast=5
Out -给定范围内的最大子阵列总和为：19
解释 -我们给出了一个包含正值和负值的数组以及从0到5的范围，即覆盖数组的所有索引。所以具有最大和的子数组可以是3+6+7+2+2-1即19。
In −intarr[]={-2,1,3,4,8,9,23},intfirst=0,intlast=3
Out -给定范围内的最大子阵列总和为：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)，将总数设置为left.total+right.total，将sub_sum设置为max({left.sub_sum,right.sub_sum,left.max_temp+right.max_val})然后返回节点。
创建一个用于构建树的方法作为build_tree。
检查IFfirst=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(节点[2*inx]，节点[2*inx+1])
创建一个方法create_tree并将temp设置为(int)(ceil(log2(size)))然后build_tree()通过传递树的节点对象，arr，值0，数组大小-1，值1来调用该方法一个论点。
创建一个方法来查找最大子数组和为maximum_sub(Tree*node,inttemp,inttemp_2,inttemp_3,inttemp_4,intinx)
检查IFtemp大于temp_4ORtemp_2小于temp_3thenreturnNULL
检查IFtemp大于temp_3ANDtemp_2小于temp_4然后返回node[inx]
调用左边的方法调用函数maximum_sub(node,temp,mid,temp_3,temp_4,2*inx)和调用maximum_sub(node,mid+1,temp_2,temp_3,temp_4,2*inx+1))
将结果设置为set_nodes(left,right)
返回结果。
创建一个方法为maximum_subarray(Tree*node,intfirst,intlast,intsize)
创建对方法的调用为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<< "给定范围内的最大子阵列总和为： "<< sub_sum;
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
给定范围内的最大子阵列总和为： 19