import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = new int[41];int sum = 0;for (int i = 1; i <= 40; i++) {arr[i] = sc.nextInt();sum += arr[i];}sc.close();int target = sum / 2; // 最接近的兩個數乘積最大long[] dp = new long[target + 1];for (int i = 1; i <= 40; i++) {for (int j = target; j >= arr[i]; j--) {dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]); // 01背包求出最接近target的數}}System.out.println(dp[target] * (sum - dp[target])); // 輸出兩組最大乘積}
}

public class Main {public static void main(String[] args) {System.out.println(12873625444L);}
}

這題其實很簡單，就是要分成兩組，然后分別對兩組求和，讓求出的兩個和乘積最大。假如所有數分成A和B兩組，那么A和B的乘積最大值就是 ((A + B) / 2) * 2，意思就是找到一組的和最接近所有數之和的一半，也就是 (A + B) / 2，那么這它與另一組數之和相乘即可得到最大乘積。