复杂度基本是O(1)级别。
对于相乘最大问题,数学上可以这么理解:如果两个数,那么理解为周长相等的矩形,正方形面积比长方形的大;如果三个数,那么理解为立方体的体积比长方体的大……以此类推。
也就是说,m个数相加等于n,找到一个数curr,curr的m次方大于等于n,那么curr就是我们要找的绳子的段数,当然最后会有一段绳子小于等于curr。具体算法如下
public class Solution { public int cutRope(int target) { if(target == 2) return 1; int curr = 1; while(true){ if(curr * curr >= target) break; curr++; } int res = 1; while(target > curr){ res *= curr; target -= curr; } res *= target; return res; } }