2015蘑菇街实习生笔试题：A+B= M

已知A,B,M都在集合S中,且满足A+B=M ,求M的最大值，并分析算法的复杂度。

#pragma once
#include <stdio.h>
#include <iostream>
using namespace std;

bool FindNumWithSum(int list[],int length,const  int sum,int &num1,int &num2)
{
if (list == NULL || length <=0)
    {
return false;
    }
int begin = 0;
int end = length - 1;
while (begin < end)
    {
long long curSum = list[begin] + list[end];
if ( curSum== sum)
        {
            num1 = list[begin];
            num2 = list[end];
return true;
        }

else if (curSum > sum)
        {
            end--;
        }
else
        {
            begin++;
        }
    }
return false;
}


void swap(int list[],int i,int j)
{
int temp = list[j];
list[j] = list[i];
list[i] = temp;
}
int Partiton(int list[],int begin,int end)
{
int p;
    p = list[begin];

while (begin < end)
    {
while (begin<end && list[end] >= p)
        {
            end--;
        }
        swap(list,begin,end);
while(begin < end && list[begin] <= p)
        {
            begin++;
        }
        swap(list,begin,end);
    }
return begin;
}

void QuickSort(int list[],int begin,int end)
{
int pivot;
if (list == NULL)
    {
return;
    }
if (begin < end)
    {
        pivot = Partiton(list,begin,end);
        QuickSort(list,begin,pivot-1);
        QuickSort(list,pivot+1 ,end);
    }
}


int comp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}

/* qsort
功 能： 使用快速排序例程进行排序
头文件：stdlib.h
用 法： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
参数： 1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针，用于确定排序的顺序
*/
void FindABM(int list[],int len)
{
if (list == NULL || len <=0 )
    {
return;
    }
// qsort(list,len,sizeof(int),comp); //使用库函数进行快排
    QuickSort(list,0,len -1);
// for (int i = 0 ; i < len ;i++)
// {
// cout<<list[i]<<ends;
// }
// cout<<endl;
int i = len -1;
for (;i >1;i--)
    {
int num1,num2;
int sum = list[i];
if (FindNumWithSum(list,i,sum,num1,num2))
        {

cout<<sum<<ends<<num1<<ends<<num2<<endl;
break;//若去掉则是输出所有可能的组合。
        }
    }
if (i == 1)
    {
cout<<"NOT FOUND"<<endl;
    }
}

void test()
{
int list[] ={3,64,33,8,1,2,4,7,11,25,36};
int len = sizeof(list)/sizeof(int);
    FindABM(list,len);
}

输出结果：
36 3 33

复杂度O(n^2)