算法 - 求子数组的最大和（C++）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法 - 求子数组的最大和（C++），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1134字，纯文字阅读大概需要2分钟。

内容图文

 

//****************************************************************************************************
//
//  求子数组的最大和 - C++ - by Chimomo
//
//  题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
//  求所有子数组的和的最大值。要求时间复杂度为O(n)。
//  例如输入的数组为5, -22, 13, 0, 45, -7, 42, -19；和最大的子数组为13, 0, 45, -7, 42；因此输出为该子数组的和93。
//
//  Answer: A traditional greedy approach.
//
//****************************************************************************************************

#include <iostream>
#include <stdio.h>

using namespace std;

int MaxSubArraySum(int a[], const int size)
{
	if(size <= 0)
	{
		length_error("Error, wrong array size.");
	}

	int sum = 0;
	int max = -(1 << 31);
	int cur = 0;

	while(cur < size)
	{
		sum += a[cur++];

		if(sum > max)
		{
			max = sum;
		}

		if(sum < 0)
		{
			sum = 0;
		}
	}

	return max;
} 

int main(int argc, char* argv[])
{
	int a[] = {0, -1, 2};
	cout << MaxSubArraySum(a, 3) << endl;

	return 0;
}

// Output:
/*
2
*/

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！希望你也加入到我们人工智能的队伍中来！http://www.captainbed.net

内容总结

以上是互联网集市为您收集整理的算法 - 求子数组的最大和（C++）全部内容，希望文章能够帮你解决算法 - 求子数组的最大和（C++）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---