53. Maximum Subarray的C++算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了53. Maximum Subarray的C++算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1417字，纯文字阅读大概需要3分钟。

内容图文

1.暴力循环，以每一个数字为起点寻找最大子数组。时间复杂度为O(n^2)

2.分治法。一个数组从中间分开，有三种情况：
A.最大数组在左边，对左半边数组再次使用分治算法。
B.最大数组在右边，对右半边数组再次使用分治算法。
C.最大数组横跨左边和右边，从中间位置向左向右找到最大值。
三种方法进行比较即可。
 

class Solution {
public:
	int maxSubArray(vector<int> &nums) {
		int res = findmax(nums, 0, nums.size()-1);
		return res;
	}
	int findmax(vector<int> &nums, int head, int tail)
	{
		if (head == tail) return nums[head];
		else{
			int mid = (head + tail) / 2;
			return max(max(findmax(nums, head, mid), findmax(nums, mid+1, tail)), findmid(nums, mid));
		}
	}
	int findmid(vector<int> &nums, int mid){
		int max1 = nums[mid];
		int sum = nums[mid];
		for (int i = mid - 1; i >= 0; i--)
		{
			sum = sum + nums[i];
			if (sum > max1) max1 = sum;
		}
		int max2 = nums[mid];
		sum = nums[mid];
		for (int i = mid + 1; i <nums.size(); i++)
		{
			sum = sum + nums[i];
			if (sum > max2) max2 = sum;
		}
		return max1 + max2 - nums[mid];
	}
};

3.动态规划。动态规划, 原数组为nums[]，设dp[i] 是以nums[i]结尾的子数组的最大和，对于元素nums[i+1], 它有两种选择：a、vec[i+1]接着前面的子数组构成最大和，b、nums[i+1]自己单独构成子数组。则dp[i+1] = max{dp[i]+nums[i+1], nums[i+1]}。

class Solution {
public:
	int maxSubArray(vector<int> &nums) {
		vector<int> dp(nums.size(),0);
		dp[0] = nums[0];
		int res = dp[0];
		for (int i = 1; i < nums.size(); i++)
		{
			dp[i] = max(dp[i - 1] + nums[i], nums[i]);
			if (dp[i]>res) res = dp[i];
		}
		return res;
	}
};

 

内容总结

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

内容备注

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

内容手机端

---