Help in problem: Combine Maximum

Given Array A of Size N,
Select any two adjacent indices, say, i and i + 1.
If A[i] == A[i+1], then you can remove A[i] and A[i+1], and put a single number in their place with value A[i] + 1.
You want to maximize the maximum number that is left in the array after applying the operation 0 or more times.

Find and return this maximum number.
Online Judge:

How to Solve this problem? I can’t find a similar problem or editorial.
I can think of brute-force that is iterate over the array, whenever find i and i+1 equal, replace it and recur or don’t replace and continue iterating.

It’s an O(n^3) Dp(Maybe). Let dp[i][j] denote whether it’s possible to compress the subarray from i to j into one number and the number itself. You can try from here. I’m making an assumption that only one such value exists. Try proving it first.

Thanks for the reply, I did try to figure out this approach of range DP, but couldn
't get how to establish the links between dp states.
for [3,3,4,4,4]:
for dp[1][5] = ?? What dp will exactly store, will it be that number if we compress entirely to a single number or in case it donesn’t range of numbers?

Keep it -1 if you can’t compress it to a single value, otherwise it should store the single value that can be created by merging all the numbers in the subarray.

Yeah, I got the intuition now. Thankyou very much.
I did try to implement the same, but getting paritally correct answer. Can you please check what I am doing wrong?

public int solve(ArrayList<Integer> A) {
        int n = A.size();
        int max=0;
        for(int x: A){
            max = Math.max(x,max);

        int dp[][] = new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = A.get(i);

        for(int l=2;l<n;l++){
            //start: i, end: i+l-1
            for(int i=0;i<=n-l;i++){

                int curr=-1;
                dp[i][i+l-1] = -1;

                for(int j=i;j<i+l-1;j++){

                    int left = dp[i][j];
                    int right = dp[j+1][i+l-1];
                    if(left==-1 || right==-1){
                    dp[i][i+l-1] = Math.max(curr, dp[i][i+l-1]);

                    max = Math.max(max,dp[i][i+l-1]);




        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         System.out.print(dp[i][j]+" ");
        //     }System.out.println();
        // }

        return max;


What if the whole array can be compressed into 1 number?

"L<=n ", got it. Thankyou very much.
Do you have list of such problems that is solved by range DP. It will be really helpful.