Find triplet having maximum product in an array

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:

• Sort binary array in linear time
• Maximum of all Subarrays of size K
• Rod Cutting Problem
• Longest subarray with sum as K
• Merge Two Sorted Arrays in-place
• WAP to Print Square Using * Character
• Merge Sort for Linked Lists
• Reverse a Linked List
• Diameter of a Binary Tree
• The Stock Span Problem