假设有数组A和B,长度为n和m
最长公共子序列
int fun(int a[],int b[],int n,int m)
{
int dp[n+1][m+1]= {0};
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(a[i-1]==b[i-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[n][m];
}
最长公共子串
int fun(int a[],int b[],int n,int m)
{
int dp[n+1][m+1]= {0};
int maxn=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(a[i-1]==b[i-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
if(maxn<dp[i][j])
maxn=dp[i][j];
}
}
return maxn;
}
最大连续子序列和
int fun(int a[],int n)
{ //例如a[3]={1,-4,2,1},输出3
int dp[n]={0};
dp[0]=a[0];
int maxn=dp[0];
for(int i=1; i<n; i++)
{
dp[i]=max(dp[i-1]+a[i],a[i]);
maxn=max(maxn,dp[i]);
}
return maxn;
}
最大非连续子序列和
int fun(int a[],int n)
{ //例如a[3]={1,-4,2,1},输出4
int maxn=a[0];
for(int i=1; i<n; i++)
{
maxn=max(maxn,maxn+a[i]);
}
return maxn;
}
最长递增序列
方法一:
int fun(int a[],int n)
{
//数据从0到n-1
int dp[n+1];
int maxn=0;
dp[0]=1;
for(int i=1; i<n; i++)
{
dp[i]=1;
for(int j=0; j<i; j++)
{
if(a[i]>a[j] && dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
}
for(int i=0; i<n; i++)
{
if(maxn<dp[i])
maxn=dp[i];
}
return maxn;
}
方法二:
//二分查找,查不到则返回当前位置
int findx(int a[],int n,int val)
{
int low=0,high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]<val)
low=mid+1;
else if(a[mid]>val)
high=mid-1;
else
return mid;
}
return low;
}
//输出最长递增序列
void fun(int a[],int n)
{
for(int i=0; i<n; i++)
{
int t=findx(st,k,a[i]);
if(t==k)
{
st[k]=a[i];
k++;
cout<<st[k-1]<<endl;
}
else
st[t]=a[i];
}
for(int i=0; i<k; i++)
cout<<st[i]<<" ";
}
平衡二叉树判断
二叉排序树判断
最后
以上就是光亮乌龟最近收集整理的关于数组问题的全部内容,更多相关数组问题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复