Recently I've been doing this USACO problem. After a while I came up with a simple idea. I'll have dp[i][j] as the maximum result from the i-th element to the j-th element, calculate each range in increasing order. If there are two subarrays [L, X] and [X+1, R] and dp[L][X] equal to dp[X+1][R], then result for dp[L][R] is dp[L][X]+1, else I will just take max(dp[L][X], dp[X+1][R]) as an answer. This seem right to me as I tested it against some small cases. But there are 12 tests in total, and I have those WAs from test (7 -> 12). The expected answer is always smaller than my output, for example, if the true answer is X, then my code output X+1. Those test case is just to large for me to check (N = 248) so I'm here asking for help. Why am I wrong ? Which mistake did I make ?

Below is my code for this problem :

#include <bits/stdc++.h>
using namespace std;

const int N = 248;
int n, a[N], dp[N][N];

int32_t main () {
	freopen("248.out", "w", stdout);
	freopen("248.in", "r", stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for (int i = 0; i < n; i++) cin>>a[i];
	for (int i = 0; i < n; i++) dp[i][i] = a[i];
	for (int len = 2; len <= n; len++) {
		for (int i = 0; i < n; i++) {
			int j = i+len-1;
			if (j >= n) break;
			for (int k = i; k < j; k++) {
				int cur_ans = max(dp[i][k], dp[k+1][j]);
				if (dp[i][k] == dp[k+1][j]) cur_ans++;
				dp[i][j] = max(dp[i][j], cur_ans);
			}
		}
	}
	cout<<dp[0][n-1];
}

And here is the jury code (Java) for this problem :

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]);
			}
		}
		pw.println(ret);
		pw.close();
	}
}

Now, I think I understand the jury idea for this problem (al least I think so, look pretty much the same as mine). But the is something that bugged me though ... In all of the accepted codes I've read of this problem, they always aim to get a maximum answer (a separate variable named ret in the jury code), while I'm trying to help an optimal answer by dp[0][N-1] (DP result of the whole array). There're some other difference like a small detail about how they calculate dp[i][j] though. I can't see the actual difference. Pls kindly point out where did I screw up ...