TopCoder SRM654 DIV1

SquareScores.java

public class SquareScores {

    double dpProb[][] = new double[1010][27];
    double dpExp[][] = new double[1010][27];

	public double calcexpectation(int[] p, String s) {
        double prob[] = new double[26];
        for (int i=0; i<26; i++) {
            if (i < p.length) {
                prob[i] = (double)(p[i]) / 100.0;
            }
        }
	    int n = s.length();
        double res = 0.0;
        for (int i=0; i<n; i++) {
            char c = s.charAt(i);
            if (c == '?') {
                for (int k=0; k<26; k++) {
                    dpProb[i+1][k] = prob[k];
                    dpExp[i+1][k] = (dpExp[i][k] + 1) * dpProb[i+1][k];
                    res += dpExp[i+1][k];
                }
            } else {
                int index = c - 'a';
                dpProb[i+1][index] = 1.0;
                dpExp[i+1][index] = dpExp[i][index] + 1;
                res += dpExp[i+1][index];
            }
        }
        return res;
	}
}

SuccessiveSubtraction2.java

public class SuccessiveSubtraction2 {

    long[] forward, forwardSeq;
    long[] backward, backwardSeq;

    public int[] calc(int[] a, int[] p, int[] v) {
        int n = a.length;
        forward = new long[n + 1];
        forwardSeq = new long[n + 1];
        backward = new long[n + 1];
        backwardSeq = new long[n + 1];
        int[] ans = new int[p.length];
        for (int i = 0; i < p.length; i++) {
            a[p[i]] = v[i];
            if (n == 1) {
                ans[i] = a[0];
                continue;
            } else if (n == 2) {
                ans[i] = a[0] - a[1];
                continue;
            }

            long sum = 0;
            for (int k = 2; k < n; k++) {
                sum += a[k];
                forwardSeq[k] = Math.max(forwardSeq[k - 1] + a[k], a[k]);
                forward[k] = Math.max(forward[k - 1], forwardSeq[k]);
            }
            backward[n] = 0;
            for (int k = n - 1; k >= 2; k--) {
                backwardSeq[k] = Math.max(backwardSeq[k + 1] + a[k], a[k]);
                backward[k] = Math.max(backward[k + 1], backwardSeq[k]);
            }
            long max = sum;
            for (int k = 2; k < n; k++) {
                long tmp = forward[k - 1] + backward[k + 1];
                max = Math.max(max, tmp);
            }
            long base = a[0] - a[1] - sum;
            ans[i] = (int) (base + 2 * max);
        }
        return ans;
    }
}