学步园

给定一个长度为N的整数数组，只允许使用乘法，不能用除法，计算任意N-1个数的组合中乘积中最大的一组，并写出算法的时间复杂度

如果数组中没有负数，编程如下：

#include "stdio.h"<br /> #include "stdlib.h"<br /> #include "time.h"<br /> #define MAXSIZE 10</p> <p>void main(){<br /> //求N-1个数的乘积的最大着<br /> int A[N];<br /> int i;<br /> int sum=1;<br /> int minpos;</p> <p> srand(time(NULL));<br /> for(i=0;i<MAXSIZE;i++){<br /> while((A[i]=rand()%MAXSIZE)==0);printf("%d ",A[i]);<br /> }//for</p> <p> for(i=1,minpos=0;i<MAXSIZE;i++){<br /> if(A[i]<A[minpos]) {sum*=A[minpos];minpos=i;}<br /> else sum*=A[i];<br /> }//for</p> <p> printf("/nN-1个数字的最大乘积是%d/n",sum);<br /> }//main

后来想到，如果有负数的话，那么程序要考虑负数，于是编程如下：

#include "stdio.h"<br /> #include "stdlib.h"<br /> #include "time.h"<br /> #define MAXSIZE 10</p> <p>void main(){<br /> //数组中可能存在负数<br /> int min,max; //min用于正数,max用于负数<br /> int A[MAXSIZE];<br /> int i,sum;<br /> int exist_0=0;</p> <p> min=max=MAXSIZE; //初始化<br /> srand(time(NULL));<br /> for(i=0;i<MAXSIZE;i++){<br /> A[i]=(rand()%MAXSIZE)-(rand()%MAXSIZE);<br /> printf("%d ",A[i]);<br /> }//for</p> <p> for(i=0,sum=1;i<MAXSIZE;i++){<br /> if(A[i]==0) {exist_0=1;continue;}<br /> if(A[i]<0){<br /> if(max==MAXSIZE) max=A[i];<br /> else{<br /> if(max<A[i]) {sum*=max;max=A[i];}<br /> else sum*=A[i];<br /> }//else<br /> }//if<br /> else {<br /> if(min==MAXSIZE) min=A[i];<br /> else{<br /> if(min>A[i]) {sum*=min;min=A[i];}<br /> else sum*=A[i];<br /> }//else<br /> }//else<br /> }//for</p> <p> if(sum>0){<br /> sum*=min;<br /> if(exist_0==1) sum=0;<br /> }//if<br /> else{<br /> if(sum<0) sum*=max;<br /> if(exist_0==1) sum*=min;<br /> }//else</p> <p> printf("/nN-1个数字的最大乘积是%d/n",sum);<br /> }//main

后来看答案，发现我和答案不一样，不过我觉得我的算法也还可以，时间复杂度嘛，貌似是O(n)……