给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
思路：
- 继续动态规划，这一题还是蛮有代表性的。从前面几题的前后一对一，二对一，提高到了n对1.
- 自顶向下的思考：第n个数对应拆分结果为，i*n-i的拆分结果 和 i*n-i的最大值。
- 得到了对应的状态转移方程：F(n) = MaX(i*(n-i) , i*F(n-i))其中I = （1到 n-1）
- 反推自底向上。F（1） = 1 F（2） = 1 ....F(n) = MaX(i*(n-i)
class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(n<=1) return 0; int[] min = new int[n]; min[0] = prices[0]; int res = 0; for(int i= 1 ; i<n ; i++){ if(prices[i] > min[i-1]) res = (int)Math.max(prices[i]-min[i-1],res); min[i] = (int)Math.min(min[i-1] , prices[i]); } return res; } }