Last Stone Weight II

1public int lastStoneWeightII(int[] stones) {
2    int total = 0;
3    for (int stone : stones) {
4        total += stone;
5    }
6
7    int target = total / 2;
8    boolean[] dp = new boolean[target + 1];
9    dp[0] = true;
10
11    for (int stone : stones) {
12        for (int j = target; j >= stone; j--) {
13            if (dp[j - stone]) {
14                dp[j] = true;
15            }
16        }
17    }
18
19    // Find largest achievable sum
20    for (int i = target; i >= 0; i--) {
21        if (dp[i]) {
22            return total - 2 * i;
23        }
24    }
25
26    return total;
27}