最大和子序列

今天来看一个简单的问题,求最大的和子序列/求最大和子数组 题目是这样的:已知序列:-2, 11, -4, 13, -5, 2, -5, -3, 12, -9,求此序列的最大子序列和

​ 其实题目很简单,但智障的我一开始弄错了,直接把所有负数提出去然后把剩下的相加,这也太简单了点吧。。。。后来想想,貌似不太对,于是,重来。一共用了三种方法。(名字都是我瞎写的)

方法一:暴力法

​ 没错,就是直接把这个数组的所有子序列的和都算一遍,跟初始最大值比较,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
int a[] = {-2,11,-4,13,-5,2,-5,-3,12,-9};
int maxSum = a[0],n = sizeof(a)/sizeof(a[0]);
for(int i = 0;i < n;i++)//子数组长度
{
for(int j = 0;j < n;j++)//子数组开始的位置,数组下标
{
int sum = 0;//记录当前子数组和
for(int k = j;k < n&&k < j + i;k++)//求和
{
sum += a[k];
}
if(sum > maxSum) maxSum = sum;
}
}
cout << "子序列的最大和是:"<< maxSum << endl;
return 0;
}

对,就是这么暴力,效率很低,时间复杂度:O(n³)

方法二:递进求和

​ 不断求出以a[i]开头的子序列的和,并在求的过程中记录好最大的子序列的和,函数代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSubArraySum(int *arr,int n)
{
int i,j,maxSum = 0,sum;
for(i = 0;i < n;i++)//子数组开始位置
{
sum = 0;
for(j = i;j < n;j++)
{
sum += arr[j];
if(sum > maxSum) maxSum = sum;//求和并比较
}
}
return maxSum;
}

相对方法一来说,方法二减少了一次遍历,时间复杂度为:O(n²)

方法三:判断求和

​ 仔细想一下,一个数,加上一个负数会变小,加上零不变,加上正数才会变大,对,就是这么简单的道理,就可以用来优化这个题的算法了。从a[0]开始累加,如果大于初始值,就替换,如果和小于零,直接舍弃,然后是a[1],函数代码如下:

1
2
3
4
5
6
7
8
9
10
11
int maxSubArraySum_2(int *arr,int n)
{
int i,maxSum = arr[0],sum = 0;
for(i = 0;i < n;i++)//子数组开始位置
{
sum += arr[i];
if(sum > maxSum) maxSum = sum;//记录最大累加和
if(sum < 0) sum = 0;//累加和小于零的不要
}
return maxSum;
}

这样的话,只要对数组遍历一次就能解决了,时间复杂度降为O(n),最简单道理往往有意想不到的效果,哈哈哈哈。

另外,加个tips: n = sizeof(a)/sizeof(a[0]),Strlen()函数不适用于整数数组