数组与矩阵：子数组的最大累加和问题（C++）

内容导读

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

内容图文

//★题目：子数组的最大累加和问题
//要求：给定一个数组arr[]，返回子数组的最大累加和。
//      时间复杂度O(N)，空间复杂度O(1)
//      例如：arr = [1,-2,3,5,-2,6,-1]，所有子数组中[3,5,-2,6]可以累加出最大的和12，return 12

#include <iostream>
#include <vector>

using namespace std;

int maxsum(vector<int> matrix);
void printVector1(vector<int> matrix);
vector<int> generateDesignated1Vector(int *arr, int size);

int main()
{
	int arrayMine[7] = { 1, -2, 3, 5 ,-2 ,6 ,-1 };//3，5，-2，6   =   12
	int *arr = arrayMine;
	vector<int> matrix = generateDesignated1Vector(arr, 7);
	printVector1(matrix);
	cout << endl;
	int result = maxsum(matrix);
	cout << result << endl;

	system("pause");
	return 0;
}

void printVector1(vector<int> matrix)
{
	int size = matrix.size();
	for (int i = 0; i < size; i++)
	{
		cout << matrix[i] << " ";
	}
}

int maxsum(vector<int> matrix)
{
	int cur = 0;
	int max = 0;
	for (int i = 0; i < matrix.size(); i++)
	{
		cur += matrix[i];
		if (cur<0)	cur = 0;
		max = max < cur ? cur : max;
	}
	return	max;
}

vector<int> generateDesignated1Vector(int *arr, int size)
{
	int setNum = 0;
	int arrIndex = 0;
	vector<int> result;
	if (size == 0)
	{
		return result;
	}
	static int vecIndex = 0;
	while (vecIndex < size)
	{
		setNum = arr[arrIndex];
		arrIndex++;
		result.push_back(setNum);
		vecIndex++;
	}
	return result;
}

内容总结

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

内容备注

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

内容手机端