Rod Cutting Problem

Medium

Problem Statement

Given a rod of length n and prices for different lengths, determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Unlimited pieces allowed.

Examples

1Example 1

Input:

{
  "price": [
    1,
    5,
    8,
    9,
    10,
    17,
    17,
    20
  ],
  "n": 8
}

Output:

22

2Example 2

Input:

{
  "price": [
    3,
    5,
    8,
    9,
    10,
    17,
    17,
    20
  ],
  "n": 8
}

Output:

24

3Example 3

Input:

{
  "price": [
    2,
    5,
    7,
    8
  ],
  "n": 4
}

Output:

10