6-7 最大子段和（分治法）

本文主要是介绍6-7 最大子段和（分治法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

6-7 最大子段和（分治法）

分数 15

全屏浏览

作者 王东

单位 贵州师范学院

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。

函数接口定义：

long long maxsubsum(int *a,int left,int right);

裁判测试程序样例：

#include <iostream>
#include<fstream>
#include <iomanip>
using namespace std;
#define N 10001long long maxsubsum(int *a,int left,int right);int main()
{int n,i;int a[N];long long sum=0;cin>>n;for(i=1;i<=n;i++)cin>>a[i];sum=maxsubsum(a,1,n);cout<<sum;return 0;
}/* 请在这里填写答案 */

输入格式:

第一行输入整数个数n（1≤n≤1000），再依次输入n个整数。

输出格式:

输出最大子段和。

输入样例1:

5
-2 11 -4 13 -5 -2

输出样例1:

20

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

函数代码：

long long maxsubsum(int *a,int left,int right){int sum=0;for(int i=left;i<right;i++){int temp=0;for(int j=i;j<right;j++){temp+=a[j];if(temp>sum)sum=temp;}}return sum;
}

这篇关于6-7 最大子段和（分治法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---