Given a rope with positive integer-length n, how to cut the rope into m integer-length parts with length p[0], p[1], ...,p[m-1], in order to get the maximal product of p[0]*p[1]* ... *p[m-1]? m is determined by you and must be greater than 0(at least one cut must be made). Return the max product you can have.

Assumptions

• n >= 2

Examples

• n = 12, the max product is 3 * 3 * 3 * 3 = 81(cut the rope into 4 pieces with length of each is 3).

Assumption: n >= 2

Approach: Dynamic Programming

Base Case: m[1] = 0, m[2] = 1;

Induction rule: m[i] represents the max product of cutting i meters rope. results = m[n];

public class Solution {
  public int maxProduct(int length) {
    // Write your solution here.
    if (length == 0 || length == 1) {
      return 0;
    }
    int[] m = new int[length + 1];
    m[1] = 0;
    m[2] = 1;
    for (int i = 3; i <= length; i++) {        
      for (int j = 1; j < i; j++) {      
        m[i] = Math.max(m[i], Math.max(j, m[j]) * (i - j));
      }                               //左大段     右小段
    }

    return m[length];
  }
}

time： n^2

space: O(n)