洛谷P1249 最大乘积（Java实现）

乘积（Java实现）"/>

洛谷P1249 最大乘积（Java实现）

题目描述
一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 n 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式
只一个正整数 n，（3≤n≤10000）。

输出格式
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

输入输出样例
输入
10
输出
2 3 5
30

解题思路：
以8和10为例，若1作因数，则显然乘积不会最大。把x分拆成若千个互不相等的自然数的和，因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把x分成2＋3….＋n直到和大于等于x，具体的贪心思路如下:

1. 若和比x大1，例如8分解为2＋3＋4=9，则因数个数至少减少1个，为了使乘积最大，应去掉最小的2，并将最后一个数(最大的数)加上1，即变为3＋5=8，此时乘积最大;
2. 若和比x大k(k≠1)，则去掉等于k的那个数，便可使乘积最大，例如10分解为2＋3＋4+5=14，去掉14-10=4，即变为2＋3＋5= 10，此时乘积最大;

分解出最优的因数后进行高精度一乘法求出答案即可。

import java.math.BigInteger;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();LinkedList<Integer> list=new LinkedList<Integer>();for(int i=2;;i++) {if(num-i>=0)list.add(i);else if(num-i==-1) {list.removeFirst();list.add(i);break;}else {list.add(i);list.remove(list.indexOf(i-num));break;}num-=i;}Collections.sort(list);BigInteger res=new BigInteger("1");for(int k:list) {res=res.multiply(new BigInteger(k+""));System.out.print(k+" ");}System.out.println();System.out.println(res);}}