can you share the link for the problem ??
Is this from some ongoing contest ??
Share the problem link first then we are going to tell us our approach.
We should confirm that it must not be from some ongoing contest.
no!! just i am solving the problem
but always the starting number should be max in order to obtain a max num
No you cant say this.
Like in example
Input-
2
61 100
The output will be 61100 , not 10061.
what about 6->63->241->11->10->100=6632411110100
as in your i/p and o/p in your solution there is a number 6 so it should come first
but i am unable to get the logic
Yes you are correct, I got a mistake in my approach.
We can use DP to solve this:
Let dp[i][j] be the max string we can make from index from i to j.
Our answer will be stored in dp[0][n-1]
Initial state will be dp[i][i] = arr[i] for i = 0 to n-1
Then for general i,j
dp[i][j] = max ( dp[i][j], dp[i][k] + dp[k+1][j], dp[k+1][j] + dp[i][k] )
Here is the function in case you want to have a look:
void solve(){
int n;
cin>>n;
vector<string> arr(n);
for(int i=0; i<n; ++i){
cin>>arr[i];
}
string dp[n][n];
for(int i=0; i<n; ++i){
dp[i][i] = arr[i];
}
for(int len=2; len<=n; ++len){
for(int i=0; i<n-len+1; ++i){
int j = i + len - 1;
dp[i][j] = "";
for(int k=i; k<j; ++k){
dp[i][j] = max<string>({ dp[i][j], dp[i][k] + dp[k+1][j], dp[k+1][j] + dp[i][k] });
}
}
}
// for(int i=0; i<n; ++i){
// for(int j=i; j<n; ++j){
// cout<<dp[i][j]<<" ";
// }
// cout<<'\n';
// }
cout<<dp[0][n-1]<<'\n';
}
dp means dynamic programming
Problem is in the domain of strings.
So maybe we can handle problem like this.
Treat numbers as strings and sort lexicographically (from highest to lowest). Print all string in this order.
LiNK to the problem
Here you can do the SUBMIT thing.
You can compare the every character of the string if it is small add it to the right else to the left. Since the constraints are too small It gonna pass easily.
bool cmp(string x, string y){
string temp1 = x.append(y);
string temp2 = y.append(x);
return temp1.compare(temp2)>0?true:false;
}
void printLargestPossibleNumber(vectorarr){
sort(arr.begin(),arr.end(),cmp);
for(int i=0;i<arr.size();i++){
cout<<arr[i];
}
}
can anyone explain the above functions
i.e.,the sort function line