数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用二分查找法查找最大子数组和的C++程序
二分查找是一种快速查找算法，其运行时间复杂度为Ο(log n)。该查找算法基于分治的思想。为了使该算法正常工作，数据集合必须已排序。
二分查找通过比较集合中最中间的项来查找特定项。如果找到匹配项，则返回该项的索引。如果中间项大于该项，则在中间项左侧的子数组中搜索该项。否则，在中间项右侧的子数组中搜索该项。此过程也继续在子数组上进行，直到子数组的大小减小到零。
这是一个使用二分查找法查找最大子数组和的程序。
算法
Begin Declare an integer function maximum() to find the maximum of two integers. Declare val1, val2 to the integer datatype. Pass them as parameter. Check the maximum between val1 and val2. Return the maximum value. End Begin Declare an integer function MCS() to find the maximum sum sub-array which includes medium of the sub-array. Declare an array array[] and variable l, m, h to the integer datatype. Pass them as parameter. Declare variable s, sum_of_left_part to the integer datatype. Initialize s = 0. Initialize 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 Declare variable sum_of_right_part to the integer datatype. Initialize 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 Declare an integer function MaximumSum_of_SubArray(). Declare an array array[] and variable l, h to the integer datatype. Pass them as parameter. Declare m to the integer datatype. 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)). Declare number_of_elements and i to the integer datatype. Print “Enter the number of elements of array: ”. Enter the value of number_of_elements. Declare an array a[number_of_elements] to the integer datatype. for(i = 0; i < n; i++) Print “Enter the element of”. Enter the data element of array. Print “Maximum sum of Sub-Array is: ” . Print the result of MaximumSum_of_SubArray(a, 0, n-1). End.
示例
#include<iostream>
using namespace std;
int maximum(int val1, int val2) // find the maximum of two integers {
return (val1 > val2)? val1:val2;
}
int MCS(int array[], int l, int m, int h) // find the maximum sum sub-array which includes medium of the sub-array. {
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; // Return sum of elements on left and right of medium.
}
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<<"Enter the number of elements of array: ";
cin>> number_of_elements;
cout<<endl;
int a[number_of_elements];
for(i = 0; i < number_of_elements; i++) {
cout<<"Enter the element of "<<i+1<<": ";
cin>>a[i];
}
cout<<"\nMaximum sum of Sub-Array is: "<<MaximumSum_of_SubArray(a, 0, number_of_elements -1); // Print the maximum sum sub-array.
return 0;
}输出
Enter the number of elements of array: 5 Enter the element of 1: 12 Enter the element of 2: 45 Enter the element of 3: 56 Enter the element of 4: 48 Enter the element of 5: 75 Maximum sum of Sub-Array is: 236
更新于：2019年7月30日
239 次浏览
广告