### Problem Statement

A group of n thieves needs some software to help them divide up their loot. A necklace must be divided up as evenly as possible among the gang members. The necklace is a circle of gems of different values.

The requirement is that the necklace be divided into n segments by cutting the necklace in n places. Every segment must contain at least one gem. The "inequity" of the division is the value of the most-valuable segment minus the value of the least-valuable segment. (The value of a segment is the sum of the values of the gems in that segment.) We want to minimize the inequity.

Create a class Necklaces that contains a method inequity that is given as input n and a int[] gems (the values of each gem in the necklace in order). The gems are in a circle, so the last element of gems is connected to the first element. The method should find the best way to divide the necklace and return the minimum possible inequity.

### Definition

 Class: Necklaces Method: inequity Parameters: int, int[] Returns: int Method signature: int inequity(int n, int[] gems) (be sure your method is public)

### Constraints

-n will be between 1 and 50 inclusive.
-gems will contain between n and 50 elements inclusive.
-Each element of gems will be between 1 and 100,000 inclusive.

### Examples

0)

 `1` `{5,12,2,9}`
`Returns: 0`
 Cut it once anywhere. There is only one segment, and its value if 28. The difference between the worst and best segment is 0 (28 - 28).
1)

 `2` `{5,12,9,2}`
`Returns: 4`
 Cut it between the 5 and 12, and also between the 12 and 9. The two resulting segments have values 12 and 9+2+5=16.
2)

 `4` `{100,92,133,201,34,34,34,94,108}`
`Returns: 29`
 Divide it as follows: 108 100 | 92 133 | 201 | 34 34 34 94. Then the result is 225 - 196.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7222&pm=3487

dgoodman

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Dynamic Programming