重要算法题代码.doc

重要算法题代码.doc一组n个数加n个乘号后最大乘积
int getNum(int *p, int begin, int end)
int t = 0;
for(int i=begin; i<=end; i++)
{
t = t * 10 + p[i];
} return t;
}
int maxM(int n, int m, int *p)
(
int i, j, k;
int val = 0;
for(i=l;i<=n;i++)
for(j=l;j<=m;j++) maxvalue[i][j] = 0;
for(i=l; i<=n; i++)
(
val = val * 10 + p[i];
maxvalue[i][0] = val;
}
for(i=2; i<=n; i++) (
for(j=l; j<=max(i-l,m); j++) (
for(k=j; k<i; k++) (
val = getNum(p, k+1, i); maxvalue[i][j] =
max(maxvalue[i][j], maxvalue[k][j-l] * val);
}
}
}
return maxvalue[n][m];
}
【i个数j个乘号，在罗列第j个乘号位置, 计算 max(k,j-l)*val] 组合问题 void printC()
{
int n = ();
for(int i=0; i<n; i++)
(
cout«v[i]«"
}
cout«endl;
〃递归的方法；
void combination(int *a, int size, int num) (
if(size<num) return;
if(num==0)
{
printC();
return;
}
(a[O]);
combination(&a[l], size-1, num-1);
();
combination(&a[l], size-1, num);
}
排列问题
递归法
void printAII(int a[], int start, int end)
{
int i;
if(start==end)
(
for(i=0; i<=end; i++)
cout«a[i]«"
cout«endl;
num++;
)
else
(
for(i=start; i<=end; i++)
{
swap2(&a[start],&a[i]);
printAII(a, start+1, end);
swap2(&a[start],&a[i]);
}
}
)
非递归
bool nextPermutationfint *a, int n)
(
int i,p,q;//p是替换点，q是交换点
i = n -1;
while(i>0 && a[i]<=a[i-l])
i--；
if(i==O) return false;
P = i；
q = i；
for(i = n -1; i>=p; i-)
if(a[i] > a[p-l] && a[i] < a[q])
q = i；
swap(a[p-l],a[q]);
for(i = n-1, q=p; q<i; i--,q++) swap(a[q],a[i]);
return true;
)
void showPermutation(int *a, int n)
(
for (int i = 0; i < n; i++)
cout« a[i];
num++;
}
最长不降序子序列
void LCS(int *a, int size)
{〃前推法O(n*n)
int *next = new int[size];
int *max = new int[size];
int i,j;
for(i=0; i<size; i++)
(
max[i] = 1;
next[i] = 0;
}
for(i = 0; i<size; i++)
(
for(j=0; j<i; j++)
if(a[i]>a[j] && max[j]+l>max[i]) max[i]=max[j]+l;
}
int large = 0;
for(i=0;i<size;i++)//求出整个数列的最长
递增子序列的长度
if(max[i] > large)
large = max[i];
cout<<"LCS:"«large«endl;
//O(nlgn)
int find(int *a,int len