Greedy Algo Problem - Find a highest product

[patrica]

Hi,

I'm trying to solve greedy algo problem listed here. Can you guys drop some hints on how can I solve this?

Thanks in advance!

Problem -

Given an array of integers, return the highest product possible by multiplying 3 numbers from the array

array of integers e.g {1, 2, 3}

array of integers e.g {1, 2, 3}

To copy to clipboard, switch view to plain text mode 

Example:

[0, -1, 3, 100, 70, 50]
 
=> 70*50*100 = 350000

[0, -1, 3, 100, 70, 50]

=> 70*50*100 = 350000

To copy to clipboard, switch view to plain text mode 

[Ginsengelf]

Hi, simple but probably not fast solution:
std::sort on the array, then multiply last three elements.

Ginsengelf

[d_stranz]

Very clever. Certainly much faster than a combinatorial method, even with the sorting.