在学习的路上，与您一同分享其中的点点滴滴！
求子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
/********************************************************************
3.求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
*********************************************************************/
/********************************************************************
问题描述符合动态规划最优子结构的要求。
关键在于转换为求出以每一个元素结尾的和最大子数组的问题求解。
设b[i]表示以a[i]结尾的子数组的最大子段和，即：
b[i]=max{sum(a[j~k])},其中0&=j&=i，j&=k&=i。
因此对于数组a[0~n]的最大字段和为max{b[i]}，其中0&=i&n。
在计算b[i]时，可以考虑以下三种情况：
1，b[i] = b[i-1]+a[i]，当b[i-1]&0时，这时候的b[i]中包含a[i]。
2，b[i] = a[i]，当b[i-1]&=0，这时候以a[i]重新作为b[i]的起点。
3，b[i]不包含a[i]的情况，这种情况在计算b[i]之前已经计算处结果，保存在b[0~i-1]中。最后计算max{b[i]}时会考虑到。
b[i] = max{b[i-1]+a[i]，a[i]}。
而数组a[0~n]则为max{b[i]}。在实现时，可以省略数组b[i]。
*********************************************************************/
bool SAMV_GetSubArraySumMax(const int *pDataArray, int nArraySize, int *pSubArrayMaxSum, int *pSubArrayBeginIndex, int *pSubArrayEndIndex)
// 参数有效性
if (pDataArray == NULL || nArraySize&=0)
// 临时变量
int bi_1 = pDataArray[0];
// 记录a0-ai_1形成的和最大自数组的和值
int maxbi = pDataArray[0];
// 记录bi_1的最大值
int subBeginIndex = 0;
int subEndIndex = 0;
int maxSubBeginIndex = 0;
int maxSubEndIndex = 0;
for (int i=1; i&nArrayS i++)
// 求得以a[i]结尾的和最大子数组值
if (bi_1 & 0)
bi_1 += pDataArray[i];
subEndIndex =
bi_1 = pDataArray[i];
subBeginIndex =
subEndIndex =
// 求所有自数组中和最大值
if (maxbi & bi_1)
maxbi = bi_1;
maxSubBeginIndex = subBeginI
maxSubEndIndex = subEndI
// 得到输出参数
if (pSubArrayMaxSum != NULL)
*pSubArrayMaxSum =
if (pSubArrayBeginIndex != NULL)
*pSubArrayBeginIndex = maxSubBeginI
if (pSubArrayEndIndex != NULL)
*pSubArrayEndIndex = maxSubEndI
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！临渊羡鱼，不如退而结网
编程之美系列之求子数组的最大和（续）
在上一篇博客中给出了连续子数组最大和的求法。现在把题目扩展一下，有以下两种情况。
PS：转载请注明出处：1、这个数组是循环的，也就是说数组首尾相连，找出连续子数组的最大和，那这个最大和可能就有一部分在最左边，有一部分在最右边。有两种处理方法：
*在数组的后面将所有的元素复制一遍，那就得到一个新的数组，这样就相当于将数组的首尾连接起来了。然后按照上一篇博客的方法，对新数组从头遍历到尾就OK了。这个方法有什么坏处呢？首先我们复制元素到数组尾的时候，内存万一不够怎么办？还有这里我们其实改变的原始数据，一般来说原始数据都是不允许改变的。
*前一种方法相当于遍历了两遍数组。既然要遍历两遍，那就按照上一篇博客中的方法，做两次循环，遍历两次数组就可以了。只在第一次遍历的开始赋初值。只给出这种方法的代码，因为更优。int GetMaxSubSum(int *arr, int nLen)
if(!arr || nLen & 1)
int sum = arr[0];
//第一次遍历
for(i = 1; i & nL ++i)
sum = max(arr[i], sum + arr[i]);
ans = max(ans, sum);
//第二次遍历，相当于由尾到头
for(i = 0; i & nL ++i)
sum = max(arr[i], sum + arr[i]);
ans = max(ans, sum);
}2、如果数组是二维的，现在需要寻找这个二维数组的一个连续的子数组的最大和，怎么搞？受前面思想的启发，可以把问题抽象成一维的情况。怎么抽象呢？如果我们知道了要取第Begin行到End行的数据，那把第Line列的Begin到End的和最为一维数组的元素，这样是不是就是一个一维的求最大和的问题啦！然后用两层循环来遍历Begin和End的所有情况就可以了。当然这里需要反复的求和，为了节省时间，预先算好二维数组的部分和PartSum，其中PartSum[i][j]表示从(0,0)到(i,j)子矩阵的和。则第Line列的第Begin到End行的和为PartSum[End][Line]
- PartSum[Begin-1][Line] - PartSum[End][Line - 1] + PartSum[Begin-1][Line - 1];//得到数组的部分和
void GetPartSum(int* arr, int* PartSum)
if(!arr || !PartSum)
for(i = 0; i & ++i)
for(j = 0; j & ++j)
PartSum[i * n + j] = arr[i * n + j];
if(i & 0 && j & 0)
PartSum[i * n + j] += PartSum[(i - 1) * n +j] + PartSum[i * n + j - 1]
- PartSum[(i - 1) * n + j - 1];
PartSum[i * n + j] += PartSum[(i - 1) * n +j];
PartSum[i * n + j] += PartSum[i * n + j - 1];
}//end for j
}//end for i
//得到第Line列，第Begin行到End行的和
int GetPartSum(int* PartSum, int Begin, int End, int Line)
if(Begin & 0 && Line & 0)
return PartSum[End * n + Line] - PartSum[(Begin - 1) * n + Line]
- PartSum[End * n + Line - 1] + PartSum[(Begin - 1) * n + Line - 1];
else if(Begin & 0)
return PartSum[End * n + Line] - PartSum[(Begin - 1) * n + Line];
else if(Line & 0)
return PartSum[End * n + Line] - PartSum[End * n + Line - 1];
return PartSum[End * n + Line];
//得到子数组的最大和
int GetMaxSubSumForTwoDim(int* arr, int* PartSum)
if(!arr || !PartSum || n & 1 || m & 1)
int Begin,End,i;
int sum,ans,M
for(Begin = 0; Begin & ++Begin)//遍历起始行
for(End = B End & ++End)//遍历终止行
sum = GetPartSum(PartSum, Begin, End, 0);
//确定好起始行和终止行之后，抽象成一维的情况
for(i = 1; i & ++i)
if(sum & 0)
sum += GetPartSum(PartSum, Begin, End, i);
ans = max(ans, sum);
}//end for i
}//end for End
Max = max(ans, Max);
}//end for Begin
}题目扩展：如果题目变成了求给定维数，比如说2*3，和最大的子矩阵，直接套上面的思路就可以了，这里不废话了。最后给出一些辅助函数及变量的定义，以及main函数的调用，不需要的可以pass：#include&stdio.h&
const int Inf = 1e5;
inline int max(const int a, const int b)
return a & b ? a :
int main()
const int N = 20;
const int M = 20;
int arr[M * N];
int PartSum[M * N];
while(scanf("%d %d", &m, &n) != EOF)
for(i = 0; i & ++i)
for(j = 0; j & ++j)
scanf("%d", &arr[i * n + j]);
GetPartSum(arr, PartSum);
printf("%d\n", GetMaxSubSumForTwoDim(arr, PartSum));
// printf("%d\n", GetMaxSubSum(arr, n));
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！用简单的语言，分享JavaSE、JVM、JavaEE的知识和心得。
C语言强化（三）求子数组的最大和
上一篇解答了在栈里面求最小值元素的问题，这一篇，来聊聊怎么找到数组中子数组的最大和。
通过这道题，你可以掌握
如何根据用户输入创建数组如何在一连串数字中找到和最大的某一段连续数字子串如何发现问题的潜在规律并利用这个规律设计算法，解决问题
连续数相加要最大，说明左右两边的数肯定不是负数，否则不可能最大连续数序列中允许存在负数，前提是负数前面的一段正数相加要大于这个负数，否则两者抵消后，和会变小算法
遇到正数，不断累加，遇到的第一个正数要记录下标
遇到负数，记录下标，把此下标减1和之前记录的正数的下标之间的数组作为一个可能最大数组，
与之前的可能最大数组比较，若变大，则取代！判断累加的值与负数大小关系如果累加值大于负数，则继续累加如果累加值小于等于负数，舍弃此负数，向前移动，累加值清零
&span style="font-size:14"&#include &stdio.h&
#include&stdlib.h&
#include &iostream&
#include&vector&
#include&sstream&
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，
因此输出为该子数组的和 18。
连续数相加要最大，说明左右两边的数肯定不是负数
连续数序列中允许存在负数，前提是负数前面的一段正数相加要大于这个负数
遇到正数，不断累加，遇到的第一个正数要记录下标
遇到负数，记录下标，
把此下标减1和之前记录的正数的下标之间的数组作为一个可能最大数组，
与之前的可能最大数组比较，若变大，则取代！
判断累加的值与负数大小关系
如果累加值大于负数，则继续累加
如果累加值小于等于负数，舍弃此负数，向前移动，累加值清零
void main()
//根据用户输入创建数组
vector &int& oriA
int n=0,count=0;
bool endFlag=
while(endFlag){
cout&&"请输入第"&&count&&"个数组元素，输入e结束输入"&&
if(str=="e"){
stringstream(str)&&
oriArray.push_back(n);
cout&&"所输入的数组为"&&
for(int i =0;i&oriArray.size();i++){
cout&&oriArray[i]&&"
//求最大子数组
add：累加值
ori：累加值的起始角标
max：最大和
maxOri：最大和子数组起始角标
maxEnd：最大和子数组结尾角标
int add=0,ori=0,max=0,maxOri=0,maxEnd=0;
bool firstPos=
for(int i =0;i&oriArray.size();i++){
//遇到正数
if(oriArray[i]&=0){
add+=oriArray[i];//不断累加
if(firstPos){//遇到的第一个正数要记录下标
//遇到负数
//之与前的可能最大和比较，若变大，则取代！
if(add&max){
maxEnd=i-1;
判断累加的值与负数大小关系
如果累加值大于负数，则继续累加
如果累加值小于等于负数，舍弃此负数，向前移动，累加值清零
if(oriArray[i]+add&0){
add+=oriArray[i];
if(i+1&oriArray.size())
//跳出循环后再判断一次
if(add&max){
maxEnd=oriArray.size()-1;
cout&&maxOri&&"
"&&maxEnd&&
cout&&"最大子数组的最大值为"&&max&&
cout&&"最大子数组为"&&
for(int i=maxOi&=maxOri&&i&=maxEi++){
cout&&oriArray[i]&&"
system("pause");
}&/span&运行图
此题的关键在于发现最大和子数组的两端不能是负数这个规律。
做完之后在网上找了找类似的题目答案，发现有大神给出了更牛的解法，在此共享一下
当前面的几个数，加起来后，b&0后，
把 b 重新赋值，置为下一个元素，b=a[i]。
当 b&sum，则更新 sum=b;
若 b&sum，则 sum 保持原值，不更新
&span style="font-size:14"&#include &stdio.h&
#include&stdlib.h&
#include &iostream&
#include&sstream&
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，
因此输出为该子数组的和 18。
当前面的几个数，加起来后，b&0后，
把 b 重新赋值，置为下一个元素，b=a[i]。
当 b&sum，则更新 sum=b;
若 b&sum，则 sum 保持原值，不更新
int maxSum(int* a, int n)
int sum=0;
for(int i=0; i&n; i++)
if(b&=0) //前面的几个数，加起来后，b&0
b=a[i];//b 重新赋值
b+=a[i];//前面的几个数，加起来后，b&=0,继续累加
sum=b;// b&sum，则更新 sum=b
void main()
int a[10]={1,-8,6,3,-1,5,7,-2,0,1};
cout&&"子数组的最大和为"&&maxSum(a,10)&&
system("pause");
}&/span&解法二之所以比解法一简练，在于他不仅仅意识到两端的数不能为负数，而且只要那一串的子数组相加小于0，就不可能是最大和子数组的一部分。
每个问题都有其发生的规律，设计算法的过程就是发现规律并加以利用的过程。
就好比打羽毛球，如果我发现只要我一回高远球，对手就放短球，那么我下次回完高远就直接冲到网前准备扑杀。
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！求子数组和的最大值
3.求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
A traditional greedy approach.
Keep current sum, slide from left to right, when sum & 0, reset sum to 0.
int maxSubarray(int a[], int size) {
if (size&=0) error(“error array size”);
int sum = 0;
int max = - (1 && 31);
int cur = 0;
while (cur & size) {
sum += a[cur++];
if (sum & max) {
} else if (sum & 0) {
要明白题意
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！求子数组的最大和（栈和队列）_百度知道
求子数组的最大和（栈和队列）
题目描述 题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数...
我有更好的答案
#include &stdio.h& #define MAX(x,y) x&y?x:y int main( ) { int arr[ ] = {1,-2,3,10,-4,7,2,-5}; int n = 8 ; //数组的长度 int sum = 0 , max = 0 ; for (int i = 0 ; i & i ++ ) { sum+=arr[i] ; max = MAX(sum,max) ; if ( sum & 0 ) sum = 0 ; } printf(&%d\n&,max);
采纳率：65%
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。}