ROCK. SPOJ - ROCK solution

Problem: www.spoj.com/problems/ROCK


Source (Java), AC:

import java.io.*;

class ROCK {

    public static int[] data;
    public static int[][] dp;

    public static int solve(int from, int to) {
        int ones = 0, zeros = 0;
        
        if(from>to)return 0;
        if (dp[from][to] != -1) return dp[from][to]; 
        
        for (int i = from; i <= to; ++i) {
            if (data[i] == 1) ones++;
            else zeros++;
        }
        
        if(ones>zeros)return dp[from][to]=ones+zeros;
         
        if(from==to) return data[to];
        int max = 0;
         
        for(int i=from;i<=to;++i){  
            int left = 0;
            if(i!=to)left = solve(from, i); 
            int right = 0;
            if(i+1!=from)right = solve(i+1, to); 
            if(left+right>max){max = left+right;}
        } 
        return dp[from][to] = max;
    }

    public static void main(String[] args) throws Exception {
        int nCases = IO.nextInt();
        while (nCases-- > 0) {
            int length = IO.nextInt();
            data = IO.nextIntArray(length, "");
            dp = new int[length + 1][length + 1];
            for (int i = 0; i < length + 1; ++i) {
                for (int j = 0; j < length + 1; ++j) {
                    dp[i][j] = -1;
                }
            }
            IO.println(solve(1, length));
        }
    }

    static class IO {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
            int[][] arr = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; ++i) {
                arr[i] = nextIntArray(cols, seperator);
            }
            return arr;
        }

        public static int[] nextIntArray(int nInts, String seperator) throws IOException {
            String ints = br.readLine();
            String[] sArray = ints.split(seperator);
            int[] array = new int[nInts + 1];
            for (int i = 1; i <= nInts; ++i) {
                array[i] = Integer.parseInt(sArray[i - 1]);
            }
            return array;
        }

        public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
            String longs = br.readLine();
            String[] sArray = longs.split(seperator);
            long[] array = new long[nLongs + 1];
            for (int i = 1; i <= nLongs; ++i) {
                array[i] = Long.parseLong(sArray[i - 1]);
            }
            return array;
        }

        public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
            String doubles = br.readLine();
            String[] sArray = doubles.split(seperator);
            double[] array = new double[nDoubles + 1];
            for (int i = 1; i <= nDoubles; ++i) {
                array[i] = Double.parseDouble(sArray[i - 1]);
            }
            return array;
        }

        public static char[] nextCharArray(int nChars, String seperator) throws IOException {
            String chars = br.readLine();
            String[] sArray = chars.split(seperator);
            char[] array = new char[nChars + 1];
            for (int i = 1; i <= nChars; ++i) {
                array[i] = sArray[i - 1].charAt(0);
            }
            return array;
        }

        public static int nextInt() throws IOException {
            String in = br.readLine();
            return Integer.parseInt(in);
        }

        public static double nextDouble() throws IOException {
            String in = br.readLine();
            return Double.parseDouble(in);
        }

        public static long nextLong() throws IOException {
            String in = br.readLine();
            return Long.parseLong(in);
        }

        public static int nextChar() throws IOException {
            String in = br.readLine();
            return in.charAt(0);
        }

        public static String nextString() throws IOException {
            return br.readLine();
        }

        public static void print(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
        }

        public static void println(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
            System.out.print("\n");
        }

        public static void printlnSeperate(String seperator, Object... o) {
            StringBuilder sb = new StringBuilder();
            sb.delete(sb.length() - seperator.length(), sb.length());
            System.out.println(sb);
        }
    }
}