最大连续子数组

时间：2024-10-09 07:06:44

最大连续子数组

  • 1 暴力法
    • 1.1 代码
    • 1.2 测试代码
    • 1.3 代码改进
      • 1.3.1 system("pause")
      • 1.3.2 输出最大和子数组 vs 最大和
      • 1.3.3 输出格式
  • 2 分治法
    • 2.1 代码
    • 2.2 测试代码
    • 2.3 复杂度分析
  • 3 分析法
    • 3.1 代码
    • 3.2 测试代码
    • 3.3 复杂度分析
  • 4 动态规划法
    • 4.1 代码
    • 4.2 测试代码
    • 4.3 时间复杂度

问题：

给定一个数组A[0,…,n-1]，求A的连续子数组，使得该数组的和最大。

exp：

数组：1,-2,3,10,-4,7,2,-5
最大子数组：3,10,-4,7,2

1 暴力法

时间复杂度为O（n3）

1.1 代码

int MaxSubArray(int *A, int n)     //最大连续子数组，参数为数组首地址和数组长度
{
	int maxSum = A[0];
	int currSum;
	for (int i = 0; i < n; i++)                //0≤i≤n-1
	{
		for (int j = i; j < n; j++)				//i≤j≤n-1
		{
			currSum = 0;
			for (int k = i; k <= j; k++)        //i≤k≤j
			{
				currSum += A[k];
			}
			if (currSum > maxSum)
				maxSum = currSum;
		}
	}
	return maxSum;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

1.2 测试代码

int main()
{
	int a[] = {  1,-2,3,10,-4,7,2,-5  };
	int len = sizeof(a) / sizeof(a[0]);
	cout<<MaxSubArray( a, len )<<endl;
	
	//替代system("pause");
	cin.clear();   //
	cin.sync();   //清空缓存区
	cin.get();    //真正接收到键盘输入

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

1.3 代码改进

1.3.1 system(“pause”)

对于输出结果一闪而过的问题未作仔细研究，后续会仔细研究如何解决。一般选择使用system("pause");语句来解决问题。但此方法据大佬说不建议使用，故而选择1.2中语句代替。参考system pause.

1.3.2 输出最大和子数组 vs 最大和

题目要求输出A的最大连续子数组，代码只求出了和。定义两个变量分别对应子数组的第一个和最后一个下标，输出子数组。方法相同，后续不再赘述。代码如下：

#include<iostream>
using namespace std;

int MaxSubArray(int *A, int n)     //最大连续子数组，参数为数组首地址和数组长度
{
	int maxSum = A[0];
	int currSum;
	int begin = 0;
	int end=0;
	for (int i = 0; i < n; i++)                //0≤i≤n-1
	{
		for (int j = i; j < n; j++)				//i≤j≤n-1
		{
			currSum = 0;
			for (int k = i; k <= j; k++)        //i≤k≤j
			{
				currSum += A[k];
			}
			if (currSum > maxSum) 
			{
				maxSum = currSum;
				begin = i; 
				end = j;
			}
		}
	}
	for (int i = begin; i < end; i++)  cout << A[i] <<',';  
	cout << A[end]<<endl;
	return 0;
}

int main()
{
	int a[] = { 1,-2,3,10,-4,7,2,-5 };
	int len = sizeof(a) / sizeof(a[0]);
	//cout << MaxSubArray(a, len) << endl;
	MaxSubArray(a, len);
	//替代system("pause");
	cin.clear();   //
	cin.sync();   //清空缓存区
	cin.get();    //真正接收到键盘输入

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

1.3.3 输出格式

还没研究，参考逗号分隔 整形 数字 输入 读取方法 C++

2 分治法

  • 将数组从中间分开，那么最大子数组要么完全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。
  • 完全在左数组、右数组，递归解决。
  • 跨立在分界点上：实际上是左数组的最大后缀和右数组的最大前缀的和。因此，在分界点上向前扫，向后扫即可。

2.1 代码

 int MaxADDSub(int*a, int from, int to) {
	if (to == from)
		return a[from];

	int middle = (from + to) / 2;
	int m1 = MaxADDSub(a, from, middle);
	int m2 = MaxADDSub(a, middle + 1, to);


	int i, left = a[middle], now = a[middle];
	for (i = middle - 1; i >= from; --i)
	{
		now += a[i];
		left = max(now, left);
	}

	int right = a[middle + 1];
	now = a[middle + 1];
	for (i = middle + 2; i <= to; ++i)
	{
		now += a[i];
		right = max(now, right);
	}
	int m3 = left + right;
	return max(m1, m2, m3);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

2.2 测试代码

int main()
{
	int a[] = { 1,-2,3,10,-4,7,2,-5 };
	int len = sizeof(a) / sizeof(a[0]);
	cout << MaxADDSub(a, 0, len - 1);			//分治法
										
	//替代system("pause");
	cin.clear();   //
	cin.sync();   //清空缓存区
	cin.get();    //真正接收到键盘输入

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2.3 复杂度分析

在这里插入图片描述

3 分析法

前缀和p[i] = a[0] + a[1] +… +a[i]
s[i,j] = p[j] - p[i-1] (定义p[-1] = 0)
算法过程：

  1. 求 i 前缀 p[i]
  • 遍历 i : 0≤ i ≤ n-1
  • p[i] = p[i-1] + A[i]
  1. 计算p[i] - p[j]
  • 遍历 i ：0≤ i ≤ n-1，求 最小值 m

m 的初值取0（p[-1] = 0）,然后遍历p[0…i-1]，更新 m

  • p[i] - m 即为以a[i]结尾的数组中最大的子数组
  1. 在第2步中，可顺手记录p[i] - m 的最大值。

3.1 代码

int MaxAddSub(int *a, int n)
{
	int result = a[0];          //最大子数组和
	int sum = a[0];             //前 i 项和
	int min = a[0];             //最小前缀
	int max = a[0];             //最大前缀

	for (int i = 1; i <= n - 1; i++)                    // 0 ≤ i ≤ n-1
	{
		sum += a[i];
		if (sum < min)
			min = sum; 	
		if (sum > max) 
			max = sum; 
		result = max - min;
	}

	return result;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

3.2 测试代码

int main()
{
	int a[] = { 1,-2,3,10,-4,7,2,-5 };
	int len = sizeof(a) / sizeof(a[0]);
	cout<< MaxAddSub(a,  len - 1);

	cin.clear();   //
	cin.sync();   //清空缓存区
	cin.get();    //真正接收到键盘输入

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.3 复杂度分析

1、2都是线性的，因此，时间复杂度O(n).

4 动态规划法

  • 记 S[i] 为以A[i] 结尾的数组中和最大的子数组
  • 则：S[i+1] = max( S[i] +A[i+1] ,A[i+1] )
  • S[0] = A[0]
  • 遍历 i：0 ≤ i ≤ n-1
  • 动态规划：最优子问题
  • 时间复杂度：O(n)

4.1 代码

int MaxAddSub(int *a, int n) {
	int result = a[0];
	int sum = a[0];
	for (int i = 0; i <= n - 1; i++) {
		if (sum > 0)
			sum += a[i];
		else
			sum = a[i];
		if (sum > result)
			result = sum;
	}
	return result;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

4.2 测试代码

int main()
{
	int a[] = { 1,-2,3,10,-4,7,2,-5 };
	int len = sizeof(a) / sizeof(a[0]);
	cout<< MaxAddSub(a,  len - 1);

	cin.clear();  
	cin.sync();   
	cin.get();    

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

4.3 时间复杂度

O(n)

相关文章