首页 > 代码库 > 求最大子数组的和，以及求该最大子数组的起始位置和末尾位置

求最大子数组的和，以及求该最大子数组的起始位置和末尾位置

2024-07-03 15:32:39   228人阅读

问题描述：

一个数组，长度为N，数组元素有负有正，如{-1， 4， 6， -3， 7， -3， -3， 9}；我们可以清楚的知道最大的子数组应该是4到9，也就是下标1到下标7，和为17。

求解思路：

第一种方法：我们可以用定义1、两个数ThisSum和MaxSum来记录当前数组的和，以及数组的最大和。

2、我们可以用两个for循环来来遍历数组，每一次求出子数组的最大和，每个子数组从0开始，下一次遍历子数组就是从1开始，以此类推。如第一次就【0~N-1】的最大和，第二次就是【1~N-1】,第三次就是【2~N】。。。。

3、这样，每次用ThisSum来记录当前数组的和，MAXSum来记录当前子数组的最大和，与ThisSum比较，取其最大就能求出最大子数组的和。

4、还是看代码吧，这样比较好理解：
int MaxSubArraySum(int a[], int N, int &start, int &end)
{
	int ThisSum, MaxSum, i, j;
	*start = 0;
	*end = 0;
	MaxSum = 0;
	for (i = 0; i < N; ++i)
	{
		ThisSum = 0;
		for (j = i; j < N; ++j)
		{
			ThisSum += a[j];
			if (ThisSum > MaxSum)
			{
				*start  = i;
				*end = j;
				MaxSum = ThisSum;
			}
		}
	}

	return MaxSum;
}
5、此方法的时间复杂度很明显为（O（N^2））

第二种算法：
思路：我们力求一种逼格最高的方法使得时间复杂度为（O(N)）.
 
1、同样我们ThisSum来记录当前子数组的和，MaxSum来记录当前子数组最大和，我们可以从0位置开始便来，开始遍历每次ThisSum 加上 a[ i ],如果当前ThisSum大于MaxSum的话，将ThisSum的值付给MaxSum，如果当前的ThisSum<0的话就把ThisSum的值赋值为0，接着下一步的遍历。

2、这里我必须说一下，求最大子数组的起点到尾端的求法，
a、我们定义start 和end来记录
b、当thisSum > maxSum时记录end 等于此时的下标。
c、当thisSum < 0时，我们可以知道起点必须从新修改，改为下一个下标（i +1）为起点start，但是要小心下一个下标(i+1)可能元素的值小于0，或者越界，所以我们必须判断一下。如：
if(i <= arr.length - 2 && arr[i+1] > 0){
start = i + 1;
}  
我们可以写出代码：
int maxSubArraySum(int[] arr, int N, int &start, int end) {
		int maxSum = 0;
		int thisSum = 0;
		int i;
		*start = 0;
		*end = 0;
		for (i = 0; i < N; i++) {
			thisSum += arr[i];
			if (thisSum > maxSum){
				maxSum = thisSum;
				*end = i;
			}
			if (thisSum < 0){
				thisSum = 0;
				if(i <= N - 2 && arr[i+1] > 0){
					*start = i + 1;
				}
			}
				
		}
		//如果最大子数组不在数组里面的话（数组元素全部<=0）,start,end赋值为-1
		if(*start == 0 && *end == 0 && arr[0] <= 0){
			*start = -1;
			*end = -1;
		}
		return maxSum;
	}


时间复杂度为（O（N））逼格满满有木有=＿=


最后一点总结：
在《数据结构与算法分析：C语言描述》中的第二章就出现这一道题，作者从（O（N^3））一路杀到（O(N)）,不得不佩服啊，有用循环和递归都有，今天我只讲两种比较典型的方法。

还有的就是作者没有求出子数组的起点以及末端，我就装逼求了一下，哈哈。


































        

            
                
                  
                
                

                    联系

                    我们