TheProduct | Topcoder Archive

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

```
{7, 4, 7}
```
```
2
```
```
1
```
```
Returns: 28
```
The maximal distance is 1, so we can't choose both 7's.
```
{7, 4, 7}
```
```
2
```
```
50
```
```
Returns: 49
```
And now it's possible.
```
{-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, 0, -2, 10, 0, 0, 3, -8, 0, 2}

Returns: 0

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.