1.源代码
#include <iostream>
#include <vector>
#include<string>
#include<sstream>
using namespace std;
int max3(int num1, int num2, int num3) {
if (num1 > num2) {
num2 = num1;
}
return num2 > num3 ? num2 : num3;
}
int max_sub_sum(vector<int> &a, int str, int end) {
if (str == end) {
if (a[str] < 0) {
return 0;
}
else {
return a[str];
}
}
else {
int max_left_sum, max_right_sum;
int mid = (str + end) / 2;
//下面的是求左右两边的子序列的最大连续子序列的和的算法
max_left_sum = max_sub_sum(a, str, mid);
max_right_sum = max_sub_sum(a, mid + 1, end);
//下面的是求中间跨越的最大连续子序列和的算法，和求左右两边的子序列的最大连续子序列的和无关
int max_left_boarder_sum = 0, max_right_boarder_sum = 0;
int left_boarder_sum = 1, right_boarder_sum = 1;
for (int i = mid; i >= str; i--) {
left_boarder_sum *= a[i];
if (left_boarder_sum > max_left_boarder_sum) {
max_left_boarder_sum = left_boarder_sum;
}
}
for (int i = mid + 1; i <= end; i++) {
right_boarder_sum *= a[i];
if (right_boarder_sum > max_right_boarder_sum) {
max_right_boarder_sum = right_boarder_sum;
}
}
int max_mid_sum = max_left_boarder_sum * max_right_boarder_sum;
return max3(max_left_sum, max_mid_sum, max_right_sum);
}
}
int main() {
cout << "第一组测试为学号(转专业)"<<endl; //学校作业
cout << "输入你要测试的组数:";
int t;
vector<int>a;
string line;
cin >> t;
int i = 1;
while (t--)
{
cout << "输入第" << i << "组要求的最大连续子序列的积的序列：";
i++;
cin.ignore();
getline(cin, line);
if (line.empty())
{
break;
}
stringstream ss(line);
int num;
while (ss >>num) //将字符串转换为整数
{
a.push_back(num);
}
int value = max_sub_sum(a, 0, a.size() - 1);
a.clear();//清空动态数组a的元素
cout << "最大连续子序列积为：" <<value << endl<<'\n';
}
system("pause");
return 0;
}
2.运行结果:
3.一张自己画的用来理解的图
