Barbie's Array of Diamonds

Question

Barbie has n diamonds. Each diamond has two attributes: shiny value and weight value. Barbie wants to create a "diamond line" in which each diamond is both shinier and heavier than the previous one.  She may not be able to use all her diamonds, but wants to maximize the number of diamonds in this diamond line.  Give a polynomial time algorithm for creating a diamond line with the maximum number of diamonds. Assume that her initial list of diamonds is not in any specific order.

Please provide the Notation, optimality, recurrence, and algorithm.

Answer 1

Let us order the diamonds by shiny value.

Now, we find the Longest Increasing Subsequence on Weight value.

Answer 2

Notation: We shall call the list diamonds[i], where i ranges from 0 to n, be the list of all of Barbie's diamonds. We also have corresponding tuple (shiny_i, weight_i) values for each i-th diamond in diamonds[i]. Let D(i) be the maximum number of diamonds in line for the i-th diamond.

Optimal Substructure: The maximum number of diamonds in line for the i-th diamond depends on the maximum number of diamonds in line for a smaller index diamond. 

Recurrence Relation: D(i) = 1 + max(D(j)) for j < i where shiny_j < shiny_i and weight_j < weight_i; or D(i) = 1 if no such j exists. 

Algorithm:

```
def barbie(diamonds):
     n = len(diamonds)

     # Initialize D(i) array, which is the DP table. Initially, each diamond forms a line with itself, therefore = 1. When D is filled, we look for max(D) as the solution for max number of diamonds in a line. 
     D = [1] * n

     # Sort diamonds by shiny value
     diamonds = sorted(diamonds, key=lambda x: x[0]) # According to wiki, Timsort worst case is O(n log n)

     # Fill DP table. Start at index 1.
     for i in range(1, n):
          for j in range(i):
               shiny_j, shiny_i = diamonds[j][0], diamonds[i][0]
               weight_j, weight_i = diamonds[j][1], diamonds[j][1]
               if (shiny_j < shiny_i) and (weight_j < weight_i):
                    D[i] = max(D[i], D[j] + 1) # Is the current line greater regardless or is there a valid diamond to add to the line?

     # Return max number of diamonds in a line found.
     return max(D)

diamonds = [(5, 10), (6, 12), (4, 8), (7, 15), (3, 5)]
barbie(diamonds) # Answer is 5 diamonds in a line. If you sort the diamonds list by shiny value, the LIS according to weight is 5.
```

Time complexity: solution runs in O(n^2 * log n)

Comments

It can be done in nlogn