P07 数组中的三数最大乘积

电玩女神 2022-10-19 12:46 138阅读 0赞

# 整数数组的三数之积 #

全正数: 1,2,3,4,5 乘积最大值(3\*4\*5)三个最大值  
全负数: -5,-4,-3,-2,-1 -1、-2、-3 三个最大值  
正负数: -1,1,2,3,4 2,3,4 三个最大值  
正负数:-4,-3,-2,-1,1 -4,-3,1 两最小、一最大

<table> 
 <thead> 
  <tr> 
   <th>情况</th> 
   <th>数组</th> 
   <th>结果</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>全正数</td> 
   <td>1,2,3,4,5</td> 
   <td>3 * 4 * 5</td> 
   <td>三个最大值</td> 
  </tr> 
  <tr> 
   <td>全负数</td> 
   <td>-5,-4,-3,-2,-1</td> 
   <td>-3 * -2 * -1</td> 
   <td>三个最大值</td> 
  </tr> 
  <tr> 
   <td>正负数</td> 
   <td>-1,1,2,3,4</td> 
   <td>2 * 3 * 4</td> 
   <td>三个最大值</td> 
  </tr> 
  <tr> 
   <td>正负数</td> 
   <td>-4,-3,-2,-1,1</td> 
   <td>-4 * -3 * 1</td> 
   <td>两最大一最小值</td> 
  </tr> 
 </tbody> 
</table>

所以结果为max((max1 \* max2 \* max3) , (min1 \* min2 \* max3))  
找出数组中的三个最大值和两个最小值即可

## 线性扫描 ##

func ProductOfThreeNumber(nums int[]) int { 
        // 属性从小到大
    	var min1, min2, max1, max2, max3 = math.MaxInt64, math.MaxInt64, math.MinInt64, math.MinInt64, math.MinInt64 
    	for _， item := range nums{ 
    		if item > max3 {         // 大于最大的，前三名依此更新属性值
    			max1 = max2
    			max2 = max3
    			max3 = item
    		}else if item > max2 {   // 仅大于第二，第二第三依此更新属性值
    			max1 = max2
    			max2 = item
    		}else if item > max1{   // 仅比第三大的大，更新当前属性值
    			max1 = item
    		}
    		if min1 > item {        // 比最小的还小，依此更新前二小属性值
    			min2 = min1
    			min1 = item
    		}else if min2 > item{   // 仅比第二小的小，更新当前属性值
    			min2 = item
    		}
    	}
    	return int(math.Max(float64(max1*max2*max3), float64(min1*min2*max3)))
    }