最大连续子数组

最大连续子数组（Maximum Subarray）问题是一个经典的算法问题，其目标是在给定的整数数组中找到一个连续的子数组，使得该子数组的元素之和最大。这个问题有多种解决方法，其中包括暴力解法、分治法和动态规划等。

下面是一个讲解最大连续子数组问题的常见解决方法：

1. 暴力解法： 暴力解法是最简单的方法，它通过两层嵌套循环遍历所有可能的子数组，计算它们的和，并找到和最大的子数组。这个方法的时间复杂度是O(n^2)，其中n是数组的长度。尽管它不是最高效的方法，但它是一个朴素而容易理解的解决方案。

2. 动态规划： 动态规划是解决最大连续子数组问题的高效方法之一。在这种方法中，我们维护一个动态规划数组dp，其中dp[i]表示以第i个元素结尾的最大子数组和。动态规划的关键是通过递推关系来计算dp[i]，这个关系通常是 dp[i] = max(dp[i-1] + nums[i], nums[i])。最终，最大子数组和就是dp数组中的最大值。这个方法的时间复杂度是O(n)，其中n是数组的长度。

3. 分治法： 分治法是另一种解决最大连续子数组问题的方法。它将数组分成三个部分：左子数组、右子数组和跨越中间的子数组。然后，递归地求解左子数组和右子数组的最大子数组和，以及跨越中间的最大子数组和。最后，将这三者中的最大值作为最终的结果。这个方法的时间复杂度是O(n*log(n))，其中n是数组的长度。

4. Kadane算法： Kadane算法是一种高效的动态规划方法，用于解决最大连续子数组问题。它维护两个变量，cur表示当前子数组的和，maxv表示最大子数组和。在遍历数组的过程中，它不断更新cur和maxv，并且当cur小于0时，将cur重置为0。最终，maxv就是最大子数组和。这个方法的时间复杂度是O(n)，其中n是数组的长度。

我们来看看代码
 

int fun04(int* p, int left, int right);
void fun()
{
	int i=0, j=0, k=0;
	int len;
	int maxv;
	int v[] = { 1,-3,6,8,0,-7,8 };
	len = 7; maxv = v[0];
	for (int i = 0; i < len; i++)
	{
		for (j = i; j < len; j++)
		{
			if (j == i)
			{
				maxv = max(maxv, v[j]);
			}
			else {
				v[i] += v[j];
				maxv = max(maxv, v[i]);
			}
			
		}
	}
	cout << maxv << endl;
}
void fun01()
{
	int v[] = { 1,-3,6,8,0,-7,8 };
	int dp[7];
	dp[0] = v[0];
	int maxv = dp[0];
	for (int i = 1; i < 7; i++)
	{
		dp[i] = max(dp[i - 1] + v[i], v[i]);
		maxv = max(maxv, dp[i]);
	}
	cout << maxv << endl;
}
 
void fun02() {
	int v[] = { -2,-1 };
	int maxv = v[0];
	int cur = 0; 
	for (int i = 0; i < 2; i++) {
		cur += v[i];
		maxv = max(maxv, cur);
		if (cur >= 0) {
			maxv = max(maxv, cur);
		}
		else {
			cur = 0;
		}
	}
	cout << maxv << endl;
}
 
void fun03() {
	int v[] = { 1,-3,6,8,0,-7,8 };
	cout << fun04(v, 0, 6);
}
int fun04(int* p, int left, int right) {
	if (left == right) {
		return p[left];
	}
	int mid = (left + right) >> 1;
	int maxleft = fun04(p, left, mid);
	int maxright = fun04(p, mid + 1, right);
 
	int tmpleft = p[mid - 1];
	int tmp = tmpleft;
	for (int i = mid - 2; i >= 0; i--) {
		tmp += p[i];
		tmpleft = max(tmp, tmpleft);
	}
 
	int tmpright = p[mid + 1];
	tmp = tmpright;
	for (int i = mid + 2; i < right; i++)
	{
		tmp += p[i];
		tmpright = max(tmp, tmpright);
	}
	int midmax = p[mid] + (tmpleft > 0 ? tmpleft : 0) + (tmpright > 0 ? tmpright : 0);
	return max(maxleft, maxright > midmax ? maxright : midmax);
}

上面的代码演示了几种不同的方法来找到数组中的最大子数组和（最大子序列和问题），并进行了简要的分析。

1. fun() 方法使用了嵌套的两个 for 循环来遍历所有可能的子数组和，同时维护最大值。这是一种朴素的暴力解法，时间复杂度为O(n^2)，其中n是数组的长度。

2. fun01() 方法使用了动态规划的思想，维护一个dp数组，其中dp[i]表示以第i个元素结尾的最大子数组和。在遍历数组的过程中，根据前一个元素的最大子数组和来计算当前元素的最大子数组和，从而避免了重复计算。这种方法的时间复杂度为O(n)，其中n是数组的长度。

3. fun02() 方法是一种更简单的方法，它遍历一次数组，同时维护当前子数组的和cur和最大子数组和maxv。当cur小于0时，表示当前子数组和不再对最大子数组和有贡献，需要将cur重置为0。这种方法也是O(n)时间复杂度。

4. fun03() 方法是一个递归的分治方法，其中 fun04() 函数采用分治思想来寻找最大子数组和。它将数组分为左右两部分，然后分别计算左部分、右部分以及跨越中间的最大子数组和，然后取三者中的最大值作为最终的结果。这个方法的时间复杂度也是O(n*log(n))，因为它每次将数组分成两半，需要进行递归处理。

总的来说，动态规划方法（fun01()和fun02()）是解决最大子数组和问题的较优解，具有O(n)的时间复杂度，而分治方法（fun03()）也是一个有效的算法，但在实际情况中可能不如动态规划方法高效。朴素的暴力解法（fun()）具有O(n^2)的时间复杂度，不适用于大规模数据。选择合适的算法取决于实际问题和性能要求。