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.