求连续子数组的最大和问题

2024-07-09 11:29| 来源: 网络整理| 查看: 265

前言

　　这几天一直在读Weiss的数据结构书(Data Structures and Algorithm Analysis in C:Second Edition)，其中第二章是关于简单的算法分析（引入大O记号等工具），以“求连续子数组的最大和问题”为例，进行了一些说明和阐释。最大子数组和问题（原书翻译为“最大的子序列和问题”）实际上我去年夏天暑假在家刷学院OJ的时候就见过，后来秋天开算法课，在上机时也有碰到。在网上看到这还是一道经典的面试题目，在此结合Weiss的书做一点总结性讨论。

问题描述

　　一个整数数组中的元素有正有负，在该数组中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2}，最大连续子数组的和为5+2-1+2=8。问题输入就是一个数组，输出该数组的“连续子数组的最大和”。

思路分析

　　这个问题我所见的有四种不同时间复杂度的算法。暴力模拟显然是最慢的，而应用动态规划思想，可以得到一个O(N)级别的线性时间算法，再它的基础上稍微变形，可以得到一个更简洁的形式。Talk is cheap, let's show codes.

代码 Solution 1: 暴力模拟，三层循环，O(n^3)级别 int MaxSubsequenceSum1(const int A[],int N) { int ThisSum=0 ,MaxSum=0,i,j,k; for(i=0;iMaxLeftBorderSum) MaxLeftBorderSum=LeftBorderSum; } MaxRightBorderSum=0; RightBorderSum=0; for(i=Center+1;iMaxRightBorderSum) MaxRightBorderSum=RightBorderSum; } //比较各种情况，求出最大值 int max1=MaxLeftSum>MaxRightSum?MaxLeftSum:MaxRightSum; int max2=MaxLeftBorderSum+MaxRightBorderSum; return max1>max2?max1:max2; }

另外一份写的更清晰的代码：

/* 求三个数中的最大值 */ int Max3(int a,int b,int c) { int Max = a; if(b > Max) Max = b; if(c > Max) Max = c; return Max; }

int MaxSubSum2(int *arr,int left,int right) { int MaxLeftSum,MaxRightSum; //左右边的最大和 int MaxLeftBorderSum,MaxRightBorderSum; //含中间边界的左右部分最大和 int LeftBorderSum,RightBorderSum; //含中间边界的左右部分当前和 int i,center; //递归到最后的基本情况 if(left == right) if(arr[left]>0) return arr[left]; else return 0; //求含中间边界的左右部分的最大值 center = (left + right)/2; MaxLeftBorderSum = 0; LeftBorderSum = 0; for(i=center;i>=left;i--) { LeftBorderSum += arr[i]; if(LeftBorderSum > MaxLeftBorderSum) MaxLeftBorderSum = LeftBorderSum; } MaxRightBorderSum = 0; RightBorderSum = 0; for(i=center+1;i MaxRightBorderSum) MaxRightBorderSum = RightBorderSum; } //递归求左右部分最大值 MaxLeftSum = MaxSubSum2(arr,left,center); MaxRightSum = MaxSubSum2(arr,center+1,right); //返回三者中的最大值 return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum); } /* 将分支策略实现的算法封装起来 */ int MaxSubSum2_1(int *arr,int len) { return MaxSubSum2(arr,0,len-1); }

以上代码时间复杂度为O(NlogN)

Solution 4: 动态规划(DP)

不难得出，针对这个问题，递推公式是DP[i] = max{DP[i-1] + A[i],A[i]}；既然转移方程出来了，意味着写一层循环就可以解决这个问题。

将这个转移方程变为形象的if-else判断，代码（来源于Weiss的书）为：

int MaxSubSum(int arr[],int len) { int i; int MaxSum = 0; int ThisSum= 0; for(i=0;i MaxSum) MaxSum = ThisSum; /*如果累加和出现小于0的情况，则和最大的子序列肯定不可能包含前面的元素，这时将累加和置0，从下个元素重新开始累加 */ else if(ThisSum< 0) ThisSum= 0; } return MaxSum; }

最后贴一份我去年暑假过学校OJ题时AC的代码。

#include #include #include using namespace std; int MaxsumUlt(int * arr, int size) { int maxSum = 0xf0000000; int sum = 0; for(int i = 0; i < size; ++i) { if(sum < 0) { sum = arr[i]; } else { sum += arr[i]; } if(sum > maxSum) { maxSum = sum; } } return maxSum; } int main(){ int n; while(cin>>n){ int a[n]; for(int i = 0;i>a[i]; printf("%d \n",MaxsumUlt(a,n)); } } 其他

　　Weiss的这本数据结构书的确不错，跟我大一下学校开数据结构课程所用的教材（两本清华出版的）简直云泥之别。只不过对于没有算法基础的初学者而言，可能会有一定难度，篇幅简略必然带来理解难度的增加。

参考资料

　　http://blog.csdn.net/ns_code/article/details/20942045

　　http://blog.sina.com.cn/s/blog_60d6fadc0101369g.html

——————————————————————————————————————

转载请注明出处，AllZY的博客园: http://www.cnblogs.com/allzy/

【本文地址】

求连续子数组的最大和问题

求连续子数组的最大和问题

今日新闻

推荐新闻