给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = {3,2,4} arr的min为2，max为9，在区间[2,9]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1，max为6，在区间[2,6]上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。
public class Solution { /** * 正数数组中的最小不可组成和 输入：正数数组arr 返回：正数数组中的最小不可组成和 */ public static int getFirstUnFormedNum(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { max += arr[i]; } for (int i = 0; i < arr.length; i++) { for (int j = 0; j + 1 < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } int min = arr[0]; int m[][] = new int[arr.length + 1][max + 1]; for (int j = min; j < max + 1; j++){ for (int i = 1; i < arr.length + 1; i++) { if (arr[i-1] <= j) { m[i][j] = Math.max(m[i - 1][j - arr[i-1]] + arr[i-1], m[i - 1][j]); } else { m[i][j] = m[i - 1][j]; } } if(m[arr.length][j]!=j){ return j; } } return max+1; } public static void main(String[] args) { int[] arr = { 2, 3, 5 }; System.out.println(Solution.getFirstUnFormedNum(arr));; } }