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
分享到:
相关推荐
key_case -- 返回字符串键名全为小写或大写的数组 array_chunk -- 将一个数组分割成多个 array_combine -- 创建一个数组,用一个数组的值作为其键名,另一个数组的值作为其值 array_count_values -- 统计数组中所有...
一个简单的大数相乘的程序,复杂度O(n平方)。
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
请不要使用除法,且在 O(n) 时间复杂度内完成此题。 示例 1: 输入: nums = [1,2,3,4] 输出: [24,12,8,6] 本测试用例为测试超时用的超长用例,数组长度为50000 如果算法调优不够,网站会在此测试用例报超时
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
要求给定一个整数数组,从数组中找出两个数的最大乘积,即 3 的倍数。 输入 {6,8,8,7,2,5} 的结果应该是 48 = 6 8。请注意,8 8 是最大的乘积 (64),但 64 不能被 3 整除。 给定输入 {1,9,2,4},结果应该是 36 = 9 4...
Java-Leetcode-乘积最大子数组.zip
示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2
[构建乘积数组]完整的可执行代码(Java) ... 题目描述: ...给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
O(1):常数时间复杂度,表示算法的运行时间不随输入数据规模n的变化而变化,始终是一个常量。 O(logn):对数时间复杂度,表示算法的运行时间与输入数据规模n的对数成正比。 O(n):线性时间复杂度,表示算法的运行...
152. 乘积最大子数组public int maxProduct(int[] nums) {//也可以用数组代替//下面mx会改变所以需要先存储起来;//三种
通过可变参数计算n个数的乘积: 代码如下: list = [] def the_input(count=eval(input("输入乘数的总个数:"))): for i in range(count): N=eval(input("依次输入乘数:")) list.append(N) ...
# 除自身以外数组的乘积 # 给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output , # 其中 output[i] 等于 nums 中除 nums[i] 之外...# 不允许使用除法 # 乘积 = 当前数左边的乘积 * 当前数右边的乘积
剑指offer面试题66--构建乘积数组给定一个数组A[0, 1,...n - 1],请构建一个数组A[0, 1,...n - 1],其中B中的元素B[i] =
学生好用的 代码,计算机体系结构实验课需要的代码,求2个二维数组积
用通常的乘法求uv的值需要O(mn)时间。我们可以将u和v均看作是有n位数字的大整数。用分治法在O(nlog3)时间内计算uv的值。当m<<n时,此法效率不高。设计算法在O(nlog2/3)时间计算uv的值 开发平台: .net ...
一个简单的代码,用于求解40以内所有能被5整除的数的乘积(和),并输出该乘积(和)。
示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24]提示:所有元素乘积之和不会溢出 32 位整数解题思路面试题66. 构建乘积数组(表
实现3-13最大k乘积问题.cpp