C ++中给定范围内的最大子数组总和
我们得到了任何给定大小的整数元素数组。任务是找到将通过从给定范围内的给定数组形成子数组来计算的最大和，该子数组可以从数组中的任何可能的索引值开始。
让我们看看这个的各种输入输出场景 -
In − int arr[] = { 3, 2, -1, 6, 7, 2 }, int first = 0, int last = 5
Out - 给定范围内的最大子阵列总和为：19
解释 - 我们给出了一个包含正值和负值的数组以及从 0 到 5 的范围，即覆盖数组的所有索引。所以具有最大和的子数组可以是 3 + 6 + 7 + 2 + 2 - 1 即 19。
In − int arr[] = {-2, 1, 3, 4, 8, 9, 23}, int first = 0, int last = 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 。
检查 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(节点[2 * inx]，节点[2 * inx + 1])
创建一个方法 create_tree 并将 temp 设置为 (int)(ceil(log2(size))) 然后build_tree()通过传递树的节点对象，arr，值 0，数组大小 -1 ，值 1 来调用该方法一个论点。
创建一个方法来查找最大子数组和为 maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx)
检查 IF temp 大于 temp_4 OR temp_2 小于 temp_3 then return NULL
检查 IF temp 大于 temp_3 AND temp_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, 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<< "给定范围内的最大子阵列总和为： "<< sub_sum;
return 0;
}
如果我们运行上面的代码，它将生成以下输出
给定范围内的最大子阵列总和为： 19
以上是 C ++中给定范围内的最大子数组总和 的全部内容， 来源链接： utcz.com/z/341267.html
