# no sort, O(n) time, O(1) space, derived idea from maxTwoProduct

• The maximum products of three elements in an array, definitely contains the maximum number in the array. Then find the rest maxTwoProduct or minTwoProduct.

``````public class Solution {
public int maximumProduct(int[] nums) {

// find the maximum number
int maxIndex = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}

// find maxTwoProduct and minTwoProduct
int maxTwo = Integer.MIN_VALUE;
int minTwo = Integer.MAX_VALUE;
int startIndex = 0;
if (maxIndex == 0) {
startIndex = 1;
}
int cur_max = nums[startIndex];
int cur_min = nums[startIndex];

for (int i = startIndex + 1; i < nums.length; i++) {
if (i == maxIndex) {
continue;
}
maxTwo = Math.max(maxTwo, Math.max(cur_max * nums[i], cur_min * nums[i]));
cur_max = Math.max(cur_max, nums[i]);
minTwo = Math.min(minTwo, Math.min(cur_max * nums[i], cur_min * nums[i]));
cur_min = Math.min(cur_min, nums[i]);
}

return Math.max(maxTwo * nums[maxIndex], minTwo * nums[maxIndex]);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.