子数组中的最大乘积

思路一

找出所有N-1个数的组合，分别计算它们的乘积，找出最大的。思路很简单，时间复杂度为很高O（N*N）

思路二

采取“空间换时间”策略，降低时间复杂度。

        数据数组为a[ ]，设置数组s[ ]，t[ ]。

        数组s[ ]的每个元素s[ i ]记录数组前i个数的乘积，s[ 0 ]设置为1

        数组t[ ]的每个元素t[ i ]记录数组后i个数的乘积，t[ 0 ]设置为1

        数组p[ ]的每个元素p[ i ]为前i-1个数和后n-i个数的乘积(即排除第i个数的其他数的乘积)

        计算p[ ]的最大值即可

view source

print?

01	int calculate(int a[],int n)

02

{

03	int sum=1;

04	int * s = (int *)malloc(sizeof(int) * (n));

05	int * t = (int *)malloc(sizeof(int) * (n));

06	int * p = (int *)malloc(sizeof(int) * (n+1));

07	s[0]=t[0]=1;

08

09

int i;

10

for(i=1;i

11

{

12	//s[i]为计算前i个数的乘积

13	s[i]=a[i-1]*s[i-1];

14	//t[i]为计算后i个数的乘积

15	t[i]=a[n-i]*t[i-1];

16

}

17

18	for(i=1;i<=n;i++)

19	//p[i]为前i-1个数和后n-i个数的乘积(即排除第i个数的其他数的乘积)

20	p[i]=s[i-1]*t[n-i];

21

22

free(s);

23

free(t);

24

free(p);

25	//max(p)求数组p的最大值,这里不实现

26	return max(p);

27

}

该算法的时间复杂度为O(n)

• 思路三

  根据数组中0，正数，负数的个数来计算

  zeroCount, pCount, nCount分别表示0，正数，负数的个数。

  1.zeroCount>0 说明最少有一个0，计算除0以外所有数的乘积记做Q，如果Q>0，返回Q，如果Q<0，说明有奇数个负数，所以0为最大值

  2.nCount(负数的个数)为奇数个，则排除绝对值最小的负数即可

  3.nCount为偶数（包含0），排除最小的正整数即可。

统计zeroCount，pCount，nCount的个数以及查找正整数最大值，负整数最大值时间复杂度都为O(n)，所以整体复杂度都为O(n)