[QQ群: 189191838，对算法和C++感兴趣可以进来]
最近一直处在放假状态当中，好些天没有更新了。晚上特意抽出几个小时过来更新几道题。
1、快速找出满足条件的两个数。(这里求出两个数之和为sum的两个数各是多少？)
这道题可以有很多考虑，我们可以的思路有：暴力解题法，每两个数字都试一试，总会有成功的，O(N*N)的复杂度。
另外一种是对每一个数字进行sum-A=B,在数组中查找到B即符合条件，这个其实是暴力解法的变形，只不过解题的表示方法不一样而已。
可能是很久以前见过这个题目吧，我第一反应就是排序(排序算法已省略)，然后左右移动，直到寻找到这两个数：复杂度是O(NlogN).
1 //result表示乘积的积，如果成功返回left,right两个数。
2 bool findAandB(elemType *list,elemType result,int &left,int &right){
3 while(left<right){
4 if(list[left]+list[right]==result){
5 return true;
6 }else if(list[left]+list[right]>result){//若大于，右边往左移
7 right--;
8 }else if(list[left]+list[right]<result){//若小于，左边往右移
9 left++;
10 }
11 }
12 return false;
13 }
2、给定一个长度为N的整形数组，其中有正有负，也有0，计算任意N-1个数的组合中乘积最大的一组。
显然，我们可以通过对每一个数进行求积，比如可以假设第一个数之外的N-1个数乘积最大，求出他们的乘积，然后再假设第二个数的乘积最大，求出乘积与前者比较，这样不断的重复，到最后总是可以找出解的。但是这种方式会有很多重复的计算，比如对很多数都需要多次乘法，造成复杂度过高。这里可以通过保存中间结果的方式进行简化时间。分别用leftList[]和rightList[]保存左右i个数的乘积，假如要求第i个数之外的N-1个数的乘积=left[i-1]*right[N-i].
1 //其中k表示除第K个数外的其他数的乘积最大。
2 void getMaxJi(elemType *list,int N,int &k){
3 int *leftList=new int[N+1];
4 int *rightList=new int[N+1];
5 leftList[0]=1,rightList[0]=1;
6 for(int i=1;i<=N;i++)//计算左边i个数的乘积
7 leftList[i]=leftList[i-1]*list[i-1];
8 for(int i=N-1,j=1;i>=0;i--,j++)//计算右边j个数的乘积
9 rightList[j]=rightList[j-1]*list[i];
10 for(int i=1;i<=N;i++)
11 if(leftList[i-1]*rightList[N-i]>max){
12 max=leftList[i-1]*rightList[N-i];
13 k=i;
14 }
15 }
当然编程之美上提供了一种更加简洁的方法，那就是统计出正数的个数，负数的个数，0的个数。这种方法的效率会更高。
3、求数组的子数组之和的最大值。
这道题可以用动态规划的思想很快解决掉，对于一维和二维的情况，我都在前面【动态规划】算法中已实现，这里就不累述了。
4、求数组中最长递增子序列，比如在序列1 -1 2 -3 4 -5 6 -7中最长为1 2 4 6或者-1 2 4 6。这里只实现最基本的解题思路O(N*N)的复杂度。
即每次求出该数字最大可以排到多大。
1 struct sequenceNum{
2 elemType paixu;
3 int preNum;
4 };
5 void getTheOrder(int *list,int N){
6 sequenceNum *B=new sequenceNum[N];
7 int currentOrder=1;
8 for(int i=0;i<N;i++)
9 B[i].paixu=1,B[i].preNum=MIN;
10 for(int i=1;i<N;i++){
11 for(int j=0;j<i;j++){
12 if(list[i]>list[j]&&B[i].paixu<=B[j].paixu){//得到一个序列表。
13 B[i].paixu=B[j].paixu+1;
14 B[i].preNum=j;
15 }
16 }
17 }
18 }
这个复杂度稍稍有点高，我们可以通过一些中间变量来计算降低比较的次数。比如说记录下当前第i个数能排的最小值。比如在上例中，第二个数为-1.那么截止第二个数，保存的最小数是-1，而不是1.
还在假期中，更新不详细And没有多讲几个算法，敬请谅解，谢谢！
版权所有，欢迎转载，但是转载请注明出处：潇一