(Analysis by Nick Wu)

This problem is solvable using dynamic programming. For each subinterval of the list, we compute the largest number we can obtain if we only use the numbers in that subinterval. If the interval has size 1, then the largest number is simply the only number in that interval. Otherwise, if that interval can be collapsed to a single number, we know that the final move consists of doing some moves in a prefix of the list, doing some moves in the corresponding suffix of that list, and then combining those numbers together. The final number that can be generated within an interval is uniquely determined, so if it is possible, then it is guaranteed that the "maximum" value attainable in that interval is the only attainable value.

Here is my Java solution.

import java.io.*;
import java.util.*;
public class two48 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("248.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("248.out")));
		int n = Integer.parseInt(br.readLine());
		int[] list = new int[n];
		for(int i = 0; i < n; i++) {
			list[i] = Integer.parseInt(br.readLine());
		int[][] dp = new int[n][n];
		int ret = 0;
		for(int len = 1; len <= n; len++) {
			for(int i = 0; i + len <= n; i++) {
				int j = i+len-1;
				dp[i][j] = -1;
				if(len == 1) {
					dp[i][j] = list[i];
				for(int k = i; k < j; k++) {
					if(dp[i][k] == dp[k+1][j] && dp[i][k] > 0) {
						dp[i][j] = Math.max(dp[i][j], dp[i][k] + 1);
				ret = Math.max(ret, dp[i][j]);