Maximum Profit from Chain Cutting

Problem Statement

Maximum Profit from Chain Cutting You are a jeweller working with a chain of precious metal. The total length of the chain is $n$, given by the length of the input array. Each possible segment length has a fixed sale value: arr[i] is the value obtained by selling one contiguous piece of length $i + 1$ (so index $0$ corresponds to length $1$, index $1$ to length $2$, …, index $n-1$ to length $n$). You may cut the chain into any number of smaller integer-length pieces (or leave it uncut). Each resulting piece of length $\ell$ is sold independently for arr[\ell - 1] . Pieces of the same length may be produced more than once. Cuts are free. Determine the maximum total profit achievable by an optimal cutting strategy. Input Format The first line contains an integer $n$ — the length of the chain (and the size of the price array). The second line contains $n$ space-separated integers arr[0] arr[1] … arr[n-1] — the sale values for lengths $1$ through $n$. Output Format Print a single integer —