当前位置:编程学习 > C/C++ >>

求数组中任意n-1个元素的最大乘积

题目描述:

给定一个整形数组a[n],求该数组中任意n-1个元素的乘积的最大值,要求不允许用除法,时间复杂度O(n),空间复杂度O(1)。

思路:求出数组中的最大负数和最小正数,然后把其他数的乘起来,如果乘积是负数,则乘以最大负数,如果乘积是正数,则乘以最小正数。

 

[cpp]
#define MAX 0x7FFFFFFF  
int maxMulit(int *a ,int n){ 
    if(a==NULL||n<=0) return 0; 
    int minp =0,minn =0,maxsum = 1, max = -MAX,min = MAX; 
    //获得最小正数和最大负数的下标  
    for(int i = 0 ;i< n; ++i){ 
        if(a[i]>= 0&& a[i]<min) { 
            minp = i; 
            min = a[i]; 
        } 
        else if(a[i]< 0&&a[i] >  max){ 
            minn = i; 
            max = a[i]; 
        } 
    } 
    for(int i = 0 ; i< n ; i++){ 
        if(i !=minn&&i !=minp){ 
            maxsum *= a[i]; 
        } 
    } 
    if(maxsum>0) maxsum *= a[minp]; 
    else maxsum *= a[minp]; 
    return maxsum; 

#define MAX 0x7FFFFFFF
int maxMulit(int *a ,int n){
 if(a==NULL||n<=0) return 0;
 int minp =0,minn =0,maxsum = 1, max = -MAX,min = MAX;
 //获得最小正数和最大负数的下标
 for(int i = 0 ;i< n; ++i){
  if(a[i]>= 0&& a[i]<min) {
   minp = i;
   min = a[i];
  }
  else if(a[i]< 0&&a[i] >  max){
   minn = i;
   max = a[i];
  }
 }
 for(int i = 0 ; i< n ; i++){
  if(i !=minn&&i !=minp){
   maxsum *= a[i];
  }
 }
 if(maxsum>0) maxsum *= a[minp];
 else maxsum *= a[minp];
 return maxsum;
}

 

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,