最近一直处在放假状态当中，好些天没有更新了。晚上特意抽出几个小时过来更新几道题。
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、求数组的子数组之和的最大值。
这道题可以用动态规划的思想很快解决掉，对于一维和二维的情况，我都在前面【动态规划】算法中已实现，这里就不累述了。
还在假期中，更新不详细And没有多讲几个算法，敬请谅解，谢谢！
版权所有，若转载，请注明出处：http://www.cnblogs.com/xiaoyi115/p/3651055.html
原文：http://www.cnblogs.com/xiaoyi115/p/3651055.html