欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

所有子数组的和的最大值

程序员文章站 2022-04-11 19:00:31
...
一、要求:
1.输入一个整形数组,数组里有正数也有负数。
2.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
3.求所有子数组的和的最大值。要求时间复杂度为O(n)

二、设计思想

先随机生成一个数组,可以限制上下限的,包括正负数的。初始化当前和的值,最大和的值,还有小组起始和结束的位置,然后循环加和,每次循环比较当前和,与,最大和的大小,当当前和小于0 的时候舍弃当前和,重新定义起始位置为下一次循环的下标值。循环结束时记录小组起始和结束的位置,然后加和输出。

五、源代码

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
#define ARYSIZE 10 //数组大小
#define MIN -30
#define MAX 30
void main()
{
	int ary[ARYSIZE];
	srand((unsigned)time(NULL));//产生随机种子
	for(int i=0;i<ARYSIZE;i++)
	{
		ary[i]=MIN+rand()%(MAX+abs(MIN)+1);
		cout<<ary[i]<<" ";
	}
	cout<<endl;
	int max=0;//保存最大和
	int curSum=0;//保存当前和
	int curStart=0;//当前和的起始位置
	int start=0;//最大和的起始位置
	int end=0;//最大和的终止位置
	for(int i=0;i<ARYSIZE;i++)
	{
		if(i==0)
		{
			curSum=max=ary[i];
			continue;
		}
			
		if(curSum<0)
		{
			curSum=0;//与负数相加,和会减小,所以抛弃以前的和
			curStart=i;
		}
		//最大值已经被保存下来,所以请大胆的继续往前加
		curSum += ary[i];
		//当前和被保存为最大值,记录下它的起始位置和结束位置
		if(curSum>max)
		{
			max=curSum;
			start=curStart;
			end=i;
		}
	}
	
	cout<<"和最大的子数组为:"<<endl;
	for(int i=start;i<=end;i++)
	{
		cout<<ary[i]<<" ";
	}
	cout<<"= "<<max;
	cout<<endl;
}

 

六、结果截图

所有子数组的和的最大值

七、总结

数据结构真的是个好东西啊