Results 1 to 3 of 3

Thread: Greedy Algo Problem - Find a highest product

  1. #1
    Join Date
    Jun 2018
    Posts
    2
    Qt products
    Qt4
    Platforms
    MacOS X

    Default Greedy Algo Problem - Find a highest product

    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

    Qt Code:
    1. array of integers e.g {1, 2, 3}
    To copy to clipboard, switch view to plain text mode 

    Example:

    Qt Code:
    1. [0, -1, 3, 100, 70, 50]
    2.  
    3. => 70*50*100 = 350000
    To copy to clipboard, switch view to plain text mode 

  2. #2
    Join Date
    Jul 2008
    Posts
    414
    Thanks
    9
    Thanked 53 Times in 51 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: Greedy Algo Problem - Find a highest product

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

    Ginsengelf

  3. The following user says thank you to Ginsengelf for this useful post:

    d_stranz (21st June 2018)

  4. #3
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    4,170
    Thanks
    235
    Thanked 662 Times in 652 Posts
    Qt products
    Qt5
    Platforms
    Windows Android

    Default Re: Greedy Algo Problem - Find a highest product

    Very clever. Certainly much faster than a combinatorial method, even with the sorting.
    <=== The Great Pumpkin says ===>
    Please use CODE tags when posting source code so it is more readable. Click "Go Advanced" and then the "#" icon to insert the tags. Paste your code between them.

Similar Threads

  1. Which architecture has the highest range of devices?
    By guidupas in forum Qt for Embedded and Mobile
    Replies: 0
    Last Post: 29th June 2015, 17:11
  2. QFile::setPermissions highest user in profiler
    By Phlucious in forum Qt Programming
    Replies: 0
    Last Post: 26th October 2012, 18:38
  3. Replies: 0
    Last Post: 4th April 2011, 17:17
  4. Non-greedy (lazy) RegExp in QtScript
    By ultr in forum Qt Programming
    Replies: 5
    Last Post: 26th May 2010, 16:40
  5. The product
    By techie1991 in forum Newbie
    Replies: 9
    Last Post: 25th March 2010, 14:54

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.