欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大

程序员文章站 2024-03-15 22:34:54
...

题目:

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)

 
输入描述:无序整数数组A[n]
输出描述:满足条件的最大乘积
输入例子: 3 4 1 2
输出例子: 
24

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		int[] x = new int[input.length()];
		char[] c = input.toCharArray();
		int y = 0;
		for (char d : c) {
			x[y] = Integer.parseInt(String.valueOf(d));
			y++;
		}
        insertSort(x);
//      for (int i : x) {
//			System.out.print(i+",");
//		}
        int temp = 1;
        for(int a=x.length-3;a<x.length; a++){
        	temp *= x[a];
        }
        System.out.println(temp);
	}
	//插入排序
	public static void insertSort(int[] a){
		int temp = 0 ,j;
        for (int i = 1; i < a.length; i++){
            if (a[i - 1] > a[i]){
                temp = a[i];
                j = i;
                while (j > 0 && a[j - 1] > temp){
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = temp;
            }
        }
    }
	
}