使用二分搜索法查找最大子数组和的 C++ 程序
c++server side programmingprogramming
二分搜索是一种快速搜索算法，运行时复杂度为 Ο(log n)。此搜索算法基于分而治之的原则。为了使此算法正常工作，数据集合应为排序形式。
二分搜索通过比较集合中最中间的项来查找特定项。如果匹配，则返回项的索引。如果中间项大于该项，则在中间项左侧的子数组中搜索该项。否则，在中间项右侧的子数组中搜索该项。这个过程在子数组上继续，直到子数组的大小减小到零。
这是使用二进制搜索方法查找最大子数组和的程序。
算法
开始 声明一个整数函数 maximum() 来查找两个整数中的最大值。 将 val1、val2 声明为整数数据类型。 将它们作为参数传递。 检查 val1 和 val2 之间的最大值。 返回最大值。 结束 开始 声明一个整数函数 MCS() 来查找包含子数组中间值的最大和子数组。 声明一个数组 array[] 并将变量 l、m、h 声明为整数数据类型。 将它们作为参数传递。 声明变量 s、sum_of_left_part 为整数数据类型。 初始化 s = 0。 初始化 sum_of_left_part = -1。 for (int i = m; i >= l; i--) s = s + array[i]。 if (s > sum_of_left_part) then sum_of_left_part = s。 s = 0 将变量 sum_of_right_part 声明为整数数据类型。 初始化 sum_of_right_part = -1。 for (int i = m+1; i <= h; i++) s = s + array[i]. if (s > sum_of_right_part) then sum_of_right_part = s。 return sum_of_left_part + sum_of_right_part。 End Begin 声明一个整数函数 MaximumSum_of_SubArray()。 将数组 array[] 和变量 l、h 声明为整数数据类型。 将它们作为参数传递。 将 m 声明为整数数据类型。 if (l == h) then return array[l]. m = (l + h)/2; return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h)). 将 number_of_elements 和 i 声明为整数数据类型。 打印"输入数组元素的数量:"。 输入number_of_elements的值。 声明一个数组a[number_of_elements]为整数数据类型。 for(i = 0; i < n; i++) 打印"输入元素"。 输入数组的数据元素。 打印"子数组的最大和为:"。 打印MaximumSum_of_SubArray(a, 0, n-1)的结果。 结束。
示例
#include<iostream>
using namespace std;
int maximum(int val1, int val2) // 查找两个整数中的最大值 {
return (val1 > val2)? val1:val2;
}
int MCS(int array[], int l, int m, int h) // 查找包含子数组中位数的最大和子数组。 {
int s = 0;
int sum_of_left_part = -1;
for (int i = m; i >= l; i--) {
s = s + array[i];
if (s > sum_of_left_part)
sum_of_left_part = s;
}
s = 0;
int sum_of_right_part = -1;
for (int i = m+1; i <= h; i++) {
s = s + array[i];
if (s > sum_of_right_part)
sum_of_right_part = s;
}
return sum_of_left_part + sum_of_right_part; // 返回中间元素左侧和右侧元素的总和。
}
int MaximumSum_of_SubArray(int array[], int l, int h) {
int m;
if (l == h)
return array[l];
m = (l + h)/2;
return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}
int main() {
int number_of_elements, i;
cout<<"请输入数组元素的个数:";
cin>> number_of_elements;
cout<<endl;
int a[number_of_elements];
for(i = 0; i < number_of_elements; i++) {
cout<<"请输入"<<i+1<<"的元素:";
cin>>a[i];
}
cout<<"\n子数组的最大和为:"<<MaximumSum_of_SubArray(a, 0, number_of_elements -1); // 打印子数组的最大和。
return 0;
}
输出
输入数组元素数:5 输入 1 的元素:12 输入 2 的元素:45 输入 3 的元素:56 输入 4 的元素:48 输入 5 的元素:75 子数组的最大和为:236
