求出整型数组s[n]中任意n-1个数的乘积的最大值,不能用除法,要求时间复杂度为o(n)

public class TestRide {
	//第一种方法
	public static long ride2(int[] data) {
		int length = data.length;
		long[] front = new long[length];// 下标i之前的数的积(不包括i)
		long[] back = new long[length];// 下标i之后的数的积(不包括i)
		front[0] = 1;
		back[length - 1] = 1;
		for (int i = 1; i < length; i++) {
			front[i] = front[i - 1] * data[i - 1];
			back[length - i - 1] = back[length - i] * data[length - i];
		}

		long result = back[0];
		for (int i = 1; i < length; i++) {
			long temp = front[i] * back[i];
			if (temp > result) {
				result = temp;
			}
		}
		return result;
	} 
	//第二种方法
	public static long ride(int[] data) {
		int pMin = 0; // 最小自然数数的下标
		int sMax = 0; // 最大负数的下标
		int sMin = 0; // 最小负数的下标
		int sSize = 0; // 负数的个数
		int zeroNum = 0; // 零的个数
		int index = 0; // 要去掉的那一个数的下标
		long result = 1; // n-1个数相乘的最大结果
		boolean pflag = true;
		boolean sflag = true;
		for (int i = 0; i < data.length; i++) {
			if (data[i] < 0) {
				sSize++;
				if (sflag) {
					sMax = i;
					sMin = i;
					sflag = false;
					continue;
				}
				if (data[sMax] < data[i]) {
					sMax = i;
				}
				if (data[sMin] > data[i]) {
					sMin = i;
				}
			} else if (data[i] >= 0) {
				if (pflag) {
					pMin = i;
					pflag = false;
				}
				if (data[i] == 0)
					zeroNum++;
				if (data[pMin] > data[i]) {
					pMin = i;
				}
			}

		}
		if (zeroNum > 1)
			return 0;
		if (sSize % 2 == 1) {
			index = sMax;
		} else if (sSize == data.length) {
			index = sMin;
		} else {
			index = pMin;
		}
		for (int i = 0; i < data.length; i++) {
			if(i == index) continue;
			result *= data[i];
		}
		return result;
	}

	public static void main(String[] args) {
		int[] data = new int[] { 5, 2, -5, 4, 9, -6, 1, 0, };
		int[] data2 = new int[] { -5, -2, -5, -4 };
		System.out.println(ride(data));
		System.out.println(ride2(data));
		System.out.println(ride(data2));
		System.out.println(ride2(data2));
	}

}

 输出结果:

10800
10800
-40
-40

上一篇:实体店老板的福音:无货源跨境电商店群,0基础上手,单人月收益5W+,模式1:1复制运营,落地教学


下一篇:go 根据文件的大小,加上单位值