编程之美系列之求子数组的连续最大积

时间：2021-01-30 20:43:04

上一篇博客编程之美系列之求子数组的最大乘积讲述了一种求最大乘积的情况，不过那个题相对来说是比较简单的，因为抽象出来之后其实也就是找出需要排除的一个数而已。OK，下面来一个题目的变形，当然这个题目也可以作为编程之美系列之求子数组的连续最大和的扩展。既然需要的子数组是连续的，也就是说是取某一段数据。怎么去决定取哪一段呢？OK，在说思路之前，先说点实际的例子来分析一下。比如说数组{-2,3,4,-3,-4},最大的数据段是{3,4,-3,-4},积为144.如果顺序调整一下，{3,-2,4,-3,-4},最大的数据段变成了{3,-2,4,-3}，积也就是72了。这里面有什么规律呢。乘积的规律都知道负负得正，尽可能的取绝对值比较大的数相乘（只要绝对值大于1，那对乘积就是有贡献的），如果有奇数，取到偶数个奇数就可以了。基于这个思路，我们来看看利用两个辅助数组来存这个结果。Pos数组来保存正数相乘的结果，Nag保存上一个负数的结果（额......怎么说呢？我觉得要表达清楚很难啊）。如果当前的数为正数（其实是0也可以放在这里），OK，直接将Pos[i+1] = arr[i]*Pos[i];Nag[i+1] = arr[I]*Nag[i];如果当前的数为负数，则交叉相乘，也就是Pos[i+1] = arr[i]*Nag[i];Nag[i+1] = arr[I]*Pos[i]。OK，这不就是递推式了么？初始状态是什么呢？后面需要连乘啊，那必然初始是1.
OK,递推式出来之后，还是不能得到我们想要的结果？为什么呢？万一乘的过程中，Pos<1了，那在乘到后面就会做出负的贡献啦。那在这里就要将数据重置为1.对已Nag也是一样的，如果大于-1，重置为1.
但是，还有什么问题呢？（能不能一次性说完呢？）如果不能有辅助内存怎么办？只能有O（1）的辅助内存。OK，任何递推式都是可以化简的嘛~~从上面的递推式可以看到第i+1个结果只与i个结果有关，这完全不需要一个数组啊，一个数就够了，不是么？理解思路之后，来看看核心代码吧~是不是很漂亮~百分之百原创。网上绝对找不到关于这道题的解答。时间复杂度是O（n），空间复杂度是O（1），应该是目前最优的了~~得意的笑，我得意的笑~~~~~~~~
举个例子来说明，就用上面说的两个，表格中红色的表示得到的最大值，箭头表示值的调整。我已经尽力的把算法讲得透彻了，不知道大家看得感觉咋样。

arr   -2 3 4 -2 -4 arr   3 -2 4 -3 -4
pos 1 -2->1 3 12 72 144 pos 1 3 -2->1 8 72 48
nag 1 -2 -6 -24 -36 -288 nag 1 3->1 -6 4 -12 -288
核心代码如下：（我很乐意贡献自己的想法，但也希望大家转载的时候注明出处： http://blog.csdn.net/kay_zhyu/article/details/8875031。谢谢~~） 

//获得（连续）子数组的最大乘积
double GetMaxProduct(double *arr, int nLen)
{
if(!arr || nLen < 1)
return -Inf;
if(nLen == 1)
return arr[0];
int i;
double ans = -Inf;
double Nag,Pos;
double temp;
Nag = Pos = 1;
for(i = 0; i < nLen; ++i)
{
if(arr[i] >= 0.0)
{
Nag *= arr[i];
Pos *= arr[i];
}
else
{
temp = Nag;
Nag = Pos * arr[i];
Pos = temp * arr[i];
}
ans = max(ans, Pos);
if(Nag > -1.0)
Nag = 1;
if(Pos < 1)
Pos = 1;
}
return ans;
}

照旧，给出辅助函数和相关变量的定义，以及main函数的调用，不需要的可以pass：

#include<stdio.h>
const double Inf = 1e5;
inline double max(const double a, const double b)
{
return a > b ? a : b;
}
int main()
{
const int N = 30;
double arr[N];
int n,i;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; ++i)
scanf("%lf", &arr[i]);
printf("%lf\n", GetMaxProduct(arr, n));
}
}

晚点给出一些测试用例，先去吃饭啦！博主吃货一枚啦~~饿死了！！！
测试用例：
1、全部小数：{0.5,0.8,-0.6,0.7,-0.7}=>0.8
2、全负数：{-5,-3,0,-1,-2,-2}=>15.
3、正负相间：即上面分析中的两个例子。
4、前正后负：{2,3,4,-5,-6}=>720.
5、正负小数都有：{2,-0.5,0.7,4,-6}=>4.

标签：

相关文章