TopCoder problem "TheProduct" used in SRM 453.5 (Division II Level Three)



Problem Statement

    

You are given an int k and a int[] numbers containing exactly N elements. Choose exactly k distinct integers between 0 and N-1, inclusive, and arrange them in ascending order. The difference between each pair of consecutive elements in this sequence must be less than or equal to maxDist. Each element in this sequence represents a zero-based index into the int[] numbers. Multiply the corresponding elements of numbers together to obtain a product. Return the maximal possible product you can get.

 

Definition

    
Class:TheProduct
Method:maxProduct
Parameters:int[], int, int
Returns:long
Method signature:long maxProduct(int[] numbers, int k, int maxDist)
(be sure your method is public)
    
 

Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between -50 and 50, inclusive.
-k will be between 1 and 10, inclusive.
-k will be less than or equal to the number of elements in numbers.
-maxDist will be between 1 and 50, inclusive.
 

Examples

0)
    
{7, 4, 7}
2
1
Returns: 28
The maximal distance is 1, so we can't choose both 7's.
1)
    
{7, 4, 7}
2
50
Returns: 49
And now it's possible.
2)
    
{-3, -5, -8, -9, -1, -2}
3
3
Returns: -10
Here, the product will always be negative, so we need to find the product with the smallest absolute value.
3)
    
{3, 0, -2, 10, 0, 0, 3, -8, 0, 2}
2
2
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10421

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14174&pm=10421

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , Xixas

Problem categories:

Greedy, Simple Math, Sorting