SRM 654 Div. 2 Hard: SuccessiveSubtraction2

問題

TopCoder Statistics - Problem Statement

解法

どのように括弧を挿入しても、a[0]は必ず正、a[1]は必ず負になる。

• a[2]からa[i]までの合計値をとる。
  • ただしa[2]からa[j]までの合計値が負になるとき、-a[2]から-a[j]までの合計値は正になるので、a[2]からa[j]までは括弧をつける必要がない。
  • この場合は、a[j+1]からa[i]までの合計値をとる。
• この合計値の最大値をとり、leftMax[i]に入れる。
• 同様にa[N-1]からa[i]までの合計値の最大値をとり、rightMax[i]に入れる。
• base=a[0]-a[1]-a[2]-...-a[N-1]とすると、base+(leftMax[i-1] + rightMax[i+1])*2 が「a[2]からa[i-1]までの間の合計値が最大になるように適当に括弧を入れ、かつ、a[i+1]からa[N-1]までの間の合計値が最大になるように適当に括弧を入れたもの」となる。

クエリに対していちいち System.gc() ならびに new int[] すると、死ぬほど遅くなるので、 Arrays.fill() で我慢しましょう。

コード

import java.util.Arrays;

public class SuccessiveSubtraction2 {

	public int[] calc(int[] a, int[] p, int[] v) {
		int n = a.length;

		int Q = p.length;
		int[] ans = new int[Q];
		int[] leftMax = new int[n];
		int[] rightMax = new int[n];
		for (int query = 0; query < Q; query++) {
			// クエリを代入する
			a[p[query]] = v[query];

			// 括弧なしの素の計算結果
			int base = a[0];
			for (int i = 1; i < n; i++) {
				base -= a[i];
			}

			Arrays.fill(leftMax, 0);
			Arrays.fill(rightMax, 0);

			int max = 0;
			int now = 0;
			for (int i = 2; i < n; i++) {
				/*
				 * a[i]の符号を変えてnow+a[i]として計算してみる。
				 * この値が負になってしまった場合は括弧を付けなければ正になるはずなので、考えなくて良い leftMax[n]:=
				 * 2からnまでの中で、a[i]の連続部分列の符号を逆にした時の最大値 要は括弧を付けて適当な連続列を括弧でくくった時の最大値
				 */
				now = Math.max(0, now + a[i]);
				max = Math.max(now, max);
				leftMax[i] = max;
			}
			max = now = 0;
			for (int i = n - 1; i >= 2; i--) {
				now = Math.max(0, now + a[i]);
				max = Math.max(now, max);
				rightMax[i] = max;
			}
			ans[query] = base + leftMax[n - 1] * 2;
			for (int i = 3; i < n - 1; i++) {
				ans[query] = Math.max(ans[query], base + (leftMax[i - 1] + rightMax[i + 1]) * 2);
			}
		}
		return ans;
	}

}