1 求最大值问题

给一个数组，求数组中的最大值

输入：A=[1,2,3,4,7,8,9]

输出：9

    1.1遍历求解   

        求解思路：最先就能够想到用遍历的方式去求解。遍历整个数组，找到最大值。

        时间复杂度分析：每次寻找都需要遍历整个数组，所以时间复杂度为O(N)

def get_max(A):
    num=len(A)
    max=A[0]
    for i in range(1,num):
        if A[i]>max:
            max=A[i]
    return max

2 寻找peak

给定数组，寻找到数组中的一个山峰值，山峰值的要求是必须同时大于他的前一位和后一位。

输入：A=[1,2,3,5,4,6,7]

输出：5

 2.1 遍历求解

        求解思路：最先就能够想到用遍历的方式去求解。遍历整个数组，找到peak。

        时间复杂度分析：最坏情况下需要遍历整个数组，所以时间复杂度为O(N)

def find_peak(A):
    num=len(A)
    peak=0
    for i in range(num):
        if A[num]<A[num-1] and A[num]>A[num+1]:
            peak=A[num]
            return peak

遍历虽然可以精准的找到数组中的peak，但是如果peak在数组的最后，那么将遍历完整个数组后才能找到。由于我们只需要返回一个peak，那有没有更简便能够定位到一个peak的方式呢，可以尝试以下二分法。

2.2 二分法求解

        求解思路：拿到数组后首先取数组中间值，判断是否是peak，是的话直接返回，不是的话则进行以下判断：

        if  A[medium]>A[medium-1] and A[medium]<A[medium+1]:  //呈现递增趋势

                在右半部分中寻找

        elif  A[medium]<A[medium-1] and A[medium]>A[medium+1]:  //呈现递减趋势

                在左半部分中寻找

        //因为在存在比中间点大的一部分，更有可能存在一个peak

        时间复杂度：由于使用的二分法，每一次寻找到中间值就会舍弃掉另一半数组，故时间复杂度为O(logN),由此可见使用二分法能够大大降低时间复杂度。同样在有序数组的查找中，室友二分法也可以大大降低时间复杂度。

def find_peak(A:list):
    num=len(A)
    medium=int((num-1)/2)
    if num==1:
        return A[0]
    elif num==2:
        return max(A)
    else:
        if A[medium]>A[medium+1] and A[medium]>A[medium-1]:
            return A[medium]
        elif A[medium]<A[medium+1] and A[medium]>A[medium-1]:
            return find_peak(A[medium+1:])
        elif A[medium]>A[medium+1] and A[medium]<A[medium-1]:
            return find_peak(A[:medium])

三、返回累加和为0的子集

题目：给定某整型数组，返回数组中累加和为0的所有子集数组

输入：A=[-7,-3,-2,5,8]

输出：[-3,-2,5]

        求解思路：

• 最能够想到的就是求出给定数组的所有的子集，在判断子集是否累加和为0，是的话则记录。
• 问题就变成了怎样才能求解一个数组的所有子集

技巧：穷举的办法

穷举[1,2,3]：[1],[2],[3],[1,2],[1,3],[2,3]

不难发现，当数组有n个元素是，穷举子集就有(2^n-1)个 ，我们可以将穷举与二进制联系起来。

3位二进制一共有 000,001,010,100,101,110,011,111 这其中排列方式，这正是与我们穷举是对应的，所以我们只需要将数组序列依次点积他对应二进制序列，就可以实现穷举。

 有了以上穷举技巧，我们不难实现：

def qiongju(A):
    n=len(A)
    res=[]
    for i in range(2**n):
        binary=str(bin(i))[2:].rjust(n-1,'0') # 转化为2进制，并补全左侧位数
        ziji=[]  #存放子集的数组
        for j in range(len(binary)):
            if binary[j]=='1':
                ziji.append(A[j])
        if sum(ziji)==0 and ziji!=[]:
            res.append(ziji)
    return res

当然穷举还有好多中方法，循环、递归都可以实现。