Subtask 1

For subtask 1, checking all subsets of rods will suffice, taking the most optimal and valid subset. To check if a subset is valid simply check all triplets of the remaining rods and verify that the triangle inequality does not hold.

An optional optimization is to notice that the easiest way to break the triangle inequality is to find the two largest rods present that is less than the ~i^{th}~ remaining rod. Sorting the rods by length in increasing order allows us to check if ~l_{i-2} + l_{i-1} > l_i~.

Time Complexity: ~\mathcal{O}(2^N \cdot N^3)~, or ~\mathcal{O}(2^N \cdot N)~ with the optimization.

Subtask 2

For subtask 2, we can build on the idea of the optional optimization using dynamic programming. Let ~dp[i][A][B]~ return the maximum value subset for the first ~i~ rods with ~A~ and ~B~ being the indices of the two largest rods being kept. To solve the original problem we can simply subtract this from the total sum of all the rod values. For the transition, we can build onto these solutions as long as the next rod we keep does not form the triangle inequality.

Time Complexity: ~\mathcal{O}(N^3)~

Subtask 3

For subtask 3, we can go for a greedy approach. In order to keep as many rods as possible, it is optimal to keep the ones with the smallest length, as this allows a greater range of possible rods to keep.

Time Complexity: ~\mathcal{O}(N \cdot \log N)~

Subtask 4

For the full solution, we can observe that with two rods we have the range of possible rods we could keep based on the triangle inequality. As the rods we loop through increase, this range increases as well. To solve for an entry in the table, rather than loop through this range we can keep track of the best solution in the range using a two-dimensional prefix max array. To maintain this range we can keep an array of integers pointing to the endpoint of the range and update it with two-pointers.

Time Complexity: ~\mathcal{O}(N^2)~