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: https://www.interviewbit.com/problems/combine-maximum

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){
curr=-1;
}else{
if(left==right){
curr=left+1;
}else{
curr=-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.