题目
动态规划
代码语言：javascript复制class Solution {
public:
string dp1[100005];
string _dp1[100005];
string dp2[100005];
string bp1[100005];
string _bp1[100005];
string bp2[100005];
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size();
int m = nums2.size();
dp2[0]="";
for(int i=1;i<=n&&i<=k;i )
{
dp2[i]="";
for(int j=n-1;j>=0;j--)
{
dp1[j]="";
if(j>n-i)
{
continue;
}
char x = '0' nums1[j];
dp1[j] = max(dp1[j 1],x _dp1[j 1]);
dp2[i]= max(dp2[i],dp1[j]);
}
for(int j=0;j<=n-1;j )
{
_dp1[j]=dp1[j];
}
}
bp2[0]="";
for(int i=1;i<=m&&i<=k;i )
{
bp2[i]="";
for(int j=m-1;j>=0;j--)
{
bp1[j]="";
if(j>m-i)
{
continue;
}
char x = '0' nums2[j];
bp1[j] = max(bp1[j 1],x _bp1[j 1]);
bp2[i]=max(bp2[i],bp1[j]);
}
for(int j=0;j<=m-1;j )
{
_bp1[j]=bp1[j];
}
}
string ans="";
for(int i=0;i<=k;i )
{
string x = dp2[i];
string y = bp2[k-i];
string str="";
int p=0;
int q=0;
while(p<x.length()||q<y.length())
{
if(p<x.length()&&q<y.length()&&x[p]>y[q])
{
str =x[p];
p ;
continue;
}
if(p<x.length()&&q<y.length()&&x[p]<y[q])
{
str =y[q];
q ;
continue;
}
if(p<x.length()&&q<y.length()&&x[p]==y[q])
{
int p1=p;
int q1=q;
int tag=0;
while(p1<x.length()||q1<y.length())
{
if(x[p1]<y[q1])
{
tag=1;
break;
}
if(x[p1]>y[q1])
{
tag=0;
break;
}
if(p1==x.length()-1&&q1==y.length()-1)
{
tag=0;
break;
}
if(p1<x.length()-1)
p1 ;
if(q1<y.length()-1)
q1 ;
}
if(tag==0)
{
str =x[p];
p ;
}
else
{
str =y[q];
q ;
}
continue;
}
if(p<x.length())
{
str =x[p];
p ;
continue;
}
if(q<y.length())
{
str =y[q];
q ;
}
}
if(ans.length()<str.length())
{
ans = str;
}
else if(ans.length()==str.length())
{
ans=max(ans,str);
}
}
vector<int> res;
for(int i=0;i<ans.length();i )
{
res.push_back(ans[i]-'0');
}
return res;
}
};
