用递归方法找一个数组中的最大值

分析

假如需要在数组[6,1,3,5,4]数组中找出其最大值，算法方法为getMax，那么结果res=getMax(6,1,3,5,4)=getMax(getMax(6,1,3),getMax(5,4))=getMax(getMax(6,1,3),getMax(5,4))=getMax(getMax(getMax(6,1),getMax(3,3)),getMax(getMax(5,5),getMax(4,4)))=...，这样就可以用递归去求解。

突破点：用什么标志递归状态？——所求数组范围的leftIndex、rightIndex。

实现

public class GetMax{
    public static int getMax(int[] arr){
        return process(arr, 0, arr.length - 1);
    }
}
// arr[L...R]范围上求最大值
public static int process(int[] arr, int L, int R){
    if(L==R){
        return arr[L];  // arr[L...R]范围上只有一个数，直接返回
    }
    int mid = L+(R-1) >>1;  // 中位
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid+1, R);
    return Math.max(leftMax, rightMax);
}
复制代码

求中点：mid = (L+R)/2，为了防止溢出，mid = L+(R-L)/2=L+(R-L)>>1 (右移比除以2更快)

Master公式

递归是非常常见的一种算法，由于递归相比顺序执行或循环程序，时间复杂度难以计算，而master公式就是用于计算递归程序的时间复杂度。

T(N)=a∗T(N/b)+O(Nd)T(N)=a*T(N/b)+O(N^d)T(N)=a∗T(N/b)+O(Nd)

• T(N)T(N)T(N)表示母问题的数据量
• T(N/b)T(N/b)T(N/b)表示子过程每次递归的数据量
• a表示子过程被调用的次数
• O(Nd)O(N^d)O(Nd)表示除去调用之外的剩余过程

满足如上公式的程序都可以根据master公式计算时间复杂度：

• log⁡ba>d\log_b{a} > dlogba>d ：时间复杂度为O(Nlog⁡ba)O(N^{\log_b{a}})O(Nlogba)
• log⁡ba=d\log_b{a} = dlogba=d ：时间复杂度为O(Nd∗logN)O(N^d * {logN})O(Nd∗logN)
• log⁡ba<d\log_b{a} < dlogba<d ：时间复杂度为O(Nd)O(N^d)O(Nd)

“用递归方法找一个数组中的最大值”的算法是否符合Master公式？

在上述的问题中，将数组分为左右两部分，每部分的计算量为N/2，这个子过程调用了2次，除去调用之外的剩余过程（即比较两部分的最大值）时间复杂度O(1)，也就是说上述的递归算法的master公式为T(N)=2∗T(N/2)+O(1)T(N)=2*T(N/2)+ O(1)T(N)=2∗T(N/2)+O(1)

归并排序是否符合Master公式？

在文章算法复杂度与简单排序算法中给出了归并排序的算法。下图给出了具体分析：

因此是满足master公式的，为T(N)=2∗T(N/2)+O(N)T(N)=2*T(N/2)+ O(N)T(N)=2∗T(N/2)+O(N)，即时间复杂度为O(N∗logN)O(N * {logN})O(N∗logN)。 因为只需要一个长度为N的临时数组，空间复杂度为O(N)O(N)O(N)。

小和问题

小和问题和逆序对问题是归并排序的算法的延伸应用。

小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：[1,3,4,2,5]中，1左边没有比1小的数；3左边有比3小的数：1；4左边比它小的数：1、3；2左边比它小的数：1；5左边比它小的数：1、3、4、2，因此小和为1+1+3+1+1+3+4+2=161+1+3+1+1+3+4+2=161+1+3+1+1+3+4+2=16

换下思路等效，也就是求每一个数右边比当前数大的个数，(个数 * 当前数) 的累加和就是结果：

在[1,3,4,2,5]中，1右边比它大的数有4个，产生4个1的小和；3右边比它大的数有2个，产生2个3的小和；4右边比它大的数有1个，产生1个4的小和；2右边比它大的数有1个，产生1个2的小和；5右边没有比它大的数。因此小和为4∗1+2∗3+1∗4+1∗2=164*1+2*3+1*4+1*2=164∗1+2∗3+1∗4+1∗2=16

第二种思路，可以轻松的用归并排序得出。下面给出具体分析步骤：

• step1:分——将数组分为左右两个部分，再递归的对子数组进行“分”操作，直到分成一个个单独的数。

• step2:合并(1,3)，左指针指向1，右指针指向3，当左侧指向值<右侧指向值时产生小和（1个1）；合并（1,3,4）时，左指针指向1，右指针指向4，产生1个1，左指针右滑到3，右指针还是指向4，产生小和（1个3）

• step3:合并（1,3,4）时，左指针指向1，右指针指向4，产生1个1，左指针右滑到3，右指针还是指向4，产生小和（1个3）

• step4:合并(2,5)，产生小和（1个2）
  网络异常，图片无法展示

  |
  
  
• step5:合并(134，25)，产生小和（2个1，1个3，1个4）
  

小和问题与归并排序

在上述小和的分析过程中，我们是手动计算右边比当前数大的数量，对于算法来说，我们就需要对数组进行排序。那小和问题与归并排序有什么关系呢？先来复习下归并排序的思路。

归并排序思路

总体思路：

• 分：把数组分为两个部分，再递归的对子数组进行“分”操作，直到分成一个个单独的数
• 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组 合并的思路：
• 新建一个空数组res，用于存放最终排序后的数组
• 比较两个有序数组的头部，较小者出队并推入res中
• 如果有两个数组还有值，重复上一步骤

不同地方

小和问题中的merge过程，如果左右相等，必须要先push右边数组的数。其它跟归并排序无差别。

public static int process(int[] arr, int l, int r){
    if(l==r){
        retun 0;
    }
    int mid = l+((r-l)>>1);
    return process(arr,l,mid)+process(arr,mid+1,r)+merge(arr,l,mid,r)
}
public static int merge(int[] arr, int l, int m, int r){
    int[] help = new int[r-l+1];
    int i=0;
    int p1=l;
    int p2=m+1;
    int res=0;
    while(p1<=m &&p2<=r){
        res+=arr[p1] <arr[p2]?(r-p2+1)*arr[p1]:0;
        help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1<=m){
        help[i++]=arr[p1++];
    }
    while(p2<=r){
        help[i++]=arr[p2++];
    }
    for(i=0;i<help.length;i++){
        arr[l+i]=help[i]
    }
    return res;
}
复制代码

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。 分析过程跟小和问题大同小异，这里暂时不详述了，详情可以点击下方链接看左神视频。

相关链接：

七天刷爆LeetCode，顶级算法大神