Problem
Find 3 numbers from the array such that their product is maximum.
Sample Input
[1,2,2,2]
Sample Output
8
Approach
We can sort the given array and end up on 2 cases:
Case 1: The maximum product is obtained by the last 3 numbers.
Case 2: The maximum product is obtained by the first 2 numbers and the last number. We just return a maximum of the above two cases. The time complexity is O(NlogN)
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int ans = max(nums[n-3]*nums[n-2]*nums[n-1],nums[0]*nums[1]*nums[n-1]);
return ans;
}
int main(){
vector<int>v{1,2,3};
cout<<maximumProduct(v);
}
Output
6
Another way to code the same algorithm in C#
using System;
public class Solution
{
public static int solve(int[] nums)
{
Array.Sort(nums);
int last = nums.Length - 1;
int C1 = nums[last] * nums[last - 1] * nums[last - 2];
int C2 = int.MinValue;
int minNegative1 = nums[0];
int minNegative2 = nums[1];
int maxValue = nums[last];
if (minNegative1 < 0 && minNegative2 < 0)
{
C2 = minNegative1 * minNegative2 * maxValue;
}
return Math.Max(C1, C2);
}
static void Main(string[] args){
int[] arr = {1, 2, 3};
Console.WriteLine(solve(arr));
}
}
Output
6
Python Programming
def maximumProduct(nums): nums.sort() return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3]) l = [1,2,3] print(maximumProduct(l))
Output
6
People are also reading:
