题目描述

题目让把长为n的绳子分为m段, 意思要自己算出来到底要分为多少段, 每段分别得多长

样例

比如长为8的绳子分为3段, 则3 3 2为最大乘积

算法1

• 第一直觉肯定每份都差不多长, 乘积最大

• 绳子最多只能分为 n/2 + 1 份

联系这两点, 就是把绳子分2份到份 n/2 + 1 份都试一遍, 尽量保持每段都一样长(每段都尽可能接近 n/m ), 就是正确答案了, 虽然不够严谨, 但符合直觉就行, 哈哈

java 代码

  public int maxProductAfterCutting(int length) {
    int max = 0;
    for (int i = 2; i <= length / 2 + 1; i++) {
      int val = getVal(length, i);
      if (max < val) max = val;
    }
    return max;
  }

  private int getVal(int length, int i) {
    if (i == 1) return length;
    int ev = length / i;
    // if (ev * i < length) ev += 1;
    return ev * getVal(length - ev, i - 1);
  }