牛客刷題-最大乘積

題目描述

給定一個無序數組，包含正數、負數和0，要求從中找出3個數的乘積，使得乘積最大，要求時間複雜度：O(n)，空間複雜度：O(1)

輸入描述:

無序整數數組A[n]      

輸出描述:

滿足條件的最大乘積      

示例1

輸入

複制

3 4 1 2      

輸出

複制

24      

吐槽一下樣例資料。。。

題目上給的輸入是沒有的n 的，實際的測試資料是有n 的即輸入資料應該是4 3 4 1 2

Java實作

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            long a[] = new long[n + 1];
            long max1 = 0, max2 = 0, max3 = 0, min1 = 0, min2 = 0;
            long temp;
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
                if (a[i] == 0)
                    continue;
                if (a[i] > 0) {
                    if (a[i] > max3) {
                        max3 = a[i];
                    }
                    if (max3 > max2) {
                        temp = max3;
                        max3 = max2;
                        max2 = temp;
                    }
                    if (max2 > max1) {
                        temp = max1;
                        max1 = max2;
                        max2 = temp;
                    }
                }
                else {
                    if (a[i] < min2) {
                        min2 = a[i];
                    }
                    if (min2 < min1) {
                        temp = min2;
                        min2 = min1;
                        min1 = temp;
                    }
                }

            }
            long f = max1;

            if (max2 * max3 > min1 * min2) {
                f = f * max2 * max3;
            } else {
                f = f * min1 * min2;
            }
            System.out.println(f);
        }
        in.close();
    }
}
           

Python 實作

import sys
n = int(sys.stdin.readline())
l=list(map(int,sys.stdin.readline().split()))
max1=0
max2=0
max3=0
min1=0
min2=0
for i in l:
    if i is 0:
        continue
    elif i >0:
        if i>max3:
            max3,i=i,max3
        if max3>max2:
            max2,max3=max3,max2
        if max2>max1:
            max1,max2=max2,max1
    else:
        if i<min2:
            min2,i=i,min2
        if min2<min1:
            min1,min2=min2,min1
print(max1*max(max2*max3,min1*min2))