java实现第九届蓝桥杯最大乘积

flowchart 箭头图标 勿删

最大乘积

把 1~9 这9个数字分成两组，中间插入乘号，

有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。

比如：

984672 * 351 = 345619872

98751 * 3462 = 341875962

9 * 87146325 = 784316925

…

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。

（只提交乘积，不要提交整个算式）

// 答案：839542176

public class Main {

	static int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	static int ans = 0;

	public static void main(String[] args) {

		f(a.length - 1);

		System.out.println(ans);

	}

	public static void f(int start) {

		if (start >= 0 && start <= 7) {

			check(start);

		}

		for (int i = start; i >= 0; i--) {

			{

				int temp = a[i];

				a[i] = a[start];

				a[start] = temp;

			}

			f(start - 1);

			{

				int temp = a[i];

				a[i] = a[start];

				a[start] = temp;

			}

		}

	}

	public static boolean check(int start) {

		String s1 = "";

		for (int i = 0; i <= start; i++) {

			s1 += a[i];

		}

		String s2 = "";

		for (int i = start + 1; i < a.length; i++) {

			s2 += a[i];

		}

		int num1 = Integer.parseInt(s1);

		int num2 = Integer.parseInt(s2);

		int sum = num1 * num2;

		if (sum < 830000000 || sum > 987654321)

			return false;

		if (!isOk(sum))

			return false;

		if (sum > ans)

			ans = sum;

		return true;

	}

	public static boolean isOk(int num) {

		String s = "" + num;

		for (int i = 1; i <= 9; i++) {

			if (s.indexOf(i + "") == -1)

				return false;

		}

		return true;

	}

}