重要算法题代码.docxVIP

一组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=1;i=n;i++)for(j=1;j=m;j++)maxvalue[i][j] = 0;for(i=1; i=n; i++) {val = val * 10 + p[i]; maxvalue[i][0] = val;}for(i=2; i=n; i++){for(j=1; j=max(i-1,m); j++){for(k=j; ki; k++){val = getNum(p, k+1, i);maxvalue[i][j] = max(maxvalue[i][j], maxvalue[k][j-1] * val);}}}return maxvalue[n][m];}【i个数j个乘号，在罗列第j个乘号位置，计算max(k,j-1)*val】组合问题void printC(){int n = v.size();for(int i=0; in; i++){coutv[i] ;}coutendl;}//递归的方法;void combination(int *a, int size, int num){if(sizenum) return;if(num==0){printC();return;}v.push_back(a[0]);combination(a[1], size-1, num-1);v.pop_back(); combination(a[1], size-1, num);}排列问题递归法void printAll(int a[], int start, int end){int i;if(start==end){for(i=0; i=end; i++)couta[i] ;coutendl;num++;}else{for(i=start; i=end; i++){swap2(a[start],a[i]);printAll(a, start+1, end);swap2(a[start],a[i]);}}}非递归bool nextPermutation(int *a, int n){int i,p,q;//p是替换点，q是交换点i = n - 1;while(i0 a[i]=a[i-1])i--;if(i==0) return false;p = i; q = i;for(i = n - 1; i=p; i--)if(a[i] a[p-1] a[i] a[q])q = i;swap(a[p-1],a[q]);for(i = n-1, q=p; qi; 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; isize; i++){ max[i] = 1;next[i] = 0;}for(i = 0; isize; i++){for(j=0; ji; j++)if(a[i]a[j] max[j]+1max[i])max[i]=max[j]+1;}int large = 0;for(i=0;isize;i++)//求出整个数列的最长递增子序列的长度if(max[i] large)large = max[i]; coutLCS:largeendl;}//O(nlgn)int find(int *a,int len,int n)//修改后的二分查找，若返回值为x，则a[x]=n{ int left=0,right=len,mid=(left+right)/2; while(left=right) { if(na[mid]) left=mid+1; else if(na[mid]) right=mid-1; else return mid; mid=(left+right)/2; } return left;}void LCS_2(int *a, int size