数据结构
网络
关系数据库管理系统 (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 次查看
