Some more progress in proving the optimality of the results for a number game; see http://math.stackexchange.com/questions/1341929

Question1341929Dynamic.java

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

public class Question1341929Dynamic {
	final static int maxn = 1000;
	final static int maxslots = 2 * maxn + 1;
	
	static class Record {
		BigInteger left;
		BigInteger right;
//		List<Integer> moves;
	
		public Record (BigInteger left,BigInteger right) {
			this.left = left;
			this.right = right;
//			moves = new ArrayList<Integer> ();
		}
		
		public Record (Record r,int i) {
			left = r.right.add (r.left);
			right = r.right.add (values [i]);
//			(moves = new ArrayList<Integer> (r.moves)).add (i - 1); 
		}
		
		public Record (int i,Record r) {
			right = r.left.add (r.right);
			left = r.left.add (values [i]);
//			(moves = new ArrayList<Integer> (r.moves)).add (i + 1); 
		}
		
		public BigInteger value () {
			return left.add (right);
		}
		
		public String toString () {
			return "<" + left + "," + right + ">";
		}
		
		public boolean dominates (Record r) {
			return left.compareTo (r.left) >= 0 && right.compareTo (r.right) >= 0;
		}
	}
	
	static class RecordSet {
		Set<Record> records = new HashSet<Record> ();
		void add (Record r) {
			if (!records.stream ().anyMatch (record -> record.dominates (r))) {
				records.removeIf (record -> r.dominates (record));
				records.add (r);
			}
		}
		
		public BigInteger value () {
			return records.stream ().map (Record::value).reduce (BigInteger.ZERO,(a,b) -> a.compareTo (b) > 0 ? a : b);
		}
		
		public String toString () {
			return records.toString ();
		}
	}
	
	// records [m] [n] contains the "best" ways to sum slots in [m,n]
	static RecordSet [] [] records = new RecordSet [maxslots] [maxslots];
	static BigInteger [] values = new BigInteger [maxslots];
	
	public static void main (String [] args) {
		for (int i = 0;i < maxslots;i++)
			values [i] = BigInteger.valueOf (Math.abs (i - maxn) + 1);
		for (int i = 0;i + 1 < maxslots;i++)
			(records [i] [i + 1] = new RecordSet ()).add (new Record (values [i],values [i + 1]));
		for (int delta = 2;delta <= 2 * maxn;delta++)
			for (int i = 0;i + delta < maxslots;i++) {
				RecordSet newRecords = new RecordSet ();
				for (Record record : records [i] [i + delta - 1].records)
					newRecords.add (new Record (record,i + delta));
				for (Record record : records [i + 1] [i + delta].records)
					newRecords.add (new Record (i,record));
				records [i] [i + delta] = newRecords;
			}
		for (int n = 2;n <= maxn;n++)
			System.out.println (n + " : " + records [maxn - (n - 1)] [maxn + (n - 1)].value ());
	}
}