Flip Array Interview Bit DP.java

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int solve(final List<Integer> A) {
        // calculate sum of A
        int sum = 0;
        int n = A.size();
        for(int x: A) sum+= x;
        sum/=2;
        
        // dp table for (N+1) X (SUM + 1)
        int dp_table[][] = new int[n+1][sum+1];
        // set int max value for sum more than 0 when we don't have any element
        for(int i=1; i<= sum;i++)dp_table[0][i] = Integer.MAX_VALUE;

        for(int i=1;i<= n;i++) {
            for(int j=1;j<= sum;j++) {
                // set the without using element choice
                dp_table[i][j] = dp_table[i-1][j];
                // when we select the element
                if(A.get(i-1) <= j && dp_table[i-1][j - A.get(i-1)] != Integer.MAX_VALUE) {
                    dp_table[i][j] = Math.min(dp_table[i][j], dp_table[i-1][j-A.get(i-1)] + 1);
                }
            }
        }
        
        // find the element which can made by suming element in array
        for(int i=sum;i>=0;i--) {
            if(dp_table[A.size()][i] != Integer.MAX_VALUE) {
                return dp_table[A.size()][i];
            }
        }
        return 0;
    }
}