Flip Array

Given an array of positive elements, you have to flip the sign of some of its elements such that the resultant sum of the elements of array should be minimum non-negative(as close to zero as possible). Return the minimum no. of elements whose sign needs to be flipped such that the resultant sum is minimum non-negative.

 1 <= n <= 100

Sum of all the elements will not exceed 10,000.

A = [15, 10, 6]

ans = 1 (Here, we will flip the sign of 15 and the resultant sum will be 1 )

A = [14, 10, 4]

ans = 1 (Here, we will flip the sign of 14 and the resultant sum will be 0)

Solution:

Time/Space: O(n^sum)

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int solve(final int[] A) {
        // p[i][sum] = for the 0 ~ ith elements, the min flip to reach positive sum
        // n[i][sum] = for the 0 ~ ith elements, the min flip to reach negative sum
        // p[i][sum] = min(p[i - 1][sum - A[i - 1]], n[i - 1][A[i - 1] - sum], p[i - 1][A[i - 1] - sum] + 1)
        // n[i][sum] = min(n[i - 1][sum - A[i - 1]], p[i - 1][sum + A[i - 1]] + 1)
        // p[0][sum] = intmax
        // p[0][0] = 0
        // find first p[n][sum] that's not int max
        int l = A.length;
        int[][] p = new int[l + 1][10001];
        int[][] n = new int[l + 1][10001]; 
        for (int i = 0; i <= l; i ++) {
            for (int j = 0; j <= 10000; j ++) {
                if (i == 0 && j == 0) continue;
                p[i][j] = Integer.MAX_VALUE;
                n[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= l; i ++) {
            int val = A[i - 1];
            for (int j = 0; j <= 10000; j ++) {
                // no flip
                if (j - val >= 0) {
                    p[i][j] = p[i - 1][j - val];
                } 
                if (val - j >= 0) {
                    p[i][j] = Math.min(p[i][j], n[i - 1][val - j]);
                }    
                
                //  flip
                if (val + j <= 10000 && p[i - 1][val + j] != Integer.MAX_VALUE) {
                    p[i][j] = Math.min(p[i][j], p[i - 1][val + j] + 1);
                }
      
                
                // no flip
                if (val + j <= 10000) {
                    n[i][j] = n[i - 1][val + j];
                }
                // flip
                if (j - val >= 0 && n[i - 1][j - val] != Integer.MAX_VALUE) {
                    n[i][j] = Math.min(n[i][j], n[i - 1][j - val] + 1);
                }
                if (val - j >= 0 && p[i - 1][val - j] != Integer.MAX_VALUE) {
                    n[i][j] = Math.min(n[i][j], p[i - 1][val - j] + 1);
                } 
        
                 
            }
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; j <= 10001; j ++) {
            if (p[l][j] != Integer.MAX_VALUE) {
                min = p[l][j];
                break;
            }
        }
        return min;
    }
}