从此篇文章入手，轻轻松松学算法

--作者: CC老师(刘依)

序言

最近想给大家更新些分治策略下的算法题解析， 有兴趣的开发者们,也可以持续关注，留言讨论。 分治策略实际上在面试中出现的非常高频，打算花一段时间给大家梳理一些题目，帮助大家能够有效地解决这一块的问题；算法最有价值的地方，其实就是在思考出解决问题的策略，并实现策略，同时去发现更优的解决方案。 "人生是长跑?， 先跑赢同龄人间的对抗"

1.1 什么是分治策略算法?

前面我们先快速了解分治策略的大致规则， 方便后续解决题目能够有一个快速的认知！

在计算机科学中，分治策略是非常重要的算法思想， 字面上的意思就是把一个复杂问题分解成2个或者多个相同或者相似的子问题，再将子问题分解成更小的子问题；直到最后的子问题可以简单地直接求解，再将子问题的结果合并得到原问题的结果。

这样的方式,比如常用的排序算法中，快速排序以及归并排序都是利用了分治策略算法的思想实现的，在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤:

1. 分解(Divide)步骤：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小;
2. 解决(Conquer)步骤：递归地求解出子问题，如果子问题的规模足够小，即停止递归，直接求解;
3. 合并(Combine)步骤：将子问题的解组合成原问题的解。

当子问题足够大, 需要递归求解时，我们就称之为"递归情况"，当子问题变的足够小，不再需要递归时， 这时递归就已经"触底"，进入了基本情况;

并不是所有的问题都能化解成完全一样的子问题， 也会出现需要求解与原问题不完全一样的子问题，接下来在这一阶段的课程，我们会看到更多基于分治策略的算法；

分治策略,在理解以及设计分治策略的算法的能力需要一定时间去掌握，它需要运用归纳法去证明一个理论，为了使得递归能够被推行，很多时候需要用一个较为概括或复杂的问题去取代原有问题，而且并没有一个系统性的方法去适当的概括问题；

分治算法需要不错的数学归纳能力，因为分治策略的算法通常需要以数学归纳法来验证， 它的计算成本则多数以求解的递归关系式来判定；

由于分治策略的特性，它最直接的表现形式常常以递归出现。

1.2 连续数列

• 难度系数: ☆☆☆
• 题目来源: LeetCode 下分治策略专题
• 题目描述: 给定一个整数数组，找出总和最大的连续数列， 并返回总和;
  • 输入: [-2,1,-3,4,-1,2,1,-5,4]
  • 输出: 6
  • 解释: 连续子数组[4,-1,2,-1]
• 题目解读:

实际上, 这个题目就是单纯的获取从一个数组中，找出连续索引值下元素相加的总和最大的序列；例如题目描述的例子，从头到尾进行查找，使得连续的元素相机得到一个最大的总和；

• 关键词: 连续数列，最大，整数数组，总和；
• 出现过企业面试题: 百度

1.2.1 暴力法

LeetCode 执行结果

暴力算法思路

• 1. 判断数组中的元素个数，如果元素个数为0，则直接返回0;
• 2. 判断数组中的元素个数，如果元素个数为1，则直接返回索引为0下的元素值;
• 3. 定义临时变量: i，temp，maxValue; 默认将maxValue 设置一个极小的值作为初始化值;
• 4. 开始循环；
• 5. 循环起始值i = 0;
• 6. 循环结束条件: 当i从头到尾都遍历了一次;
• 7. 循环递增条件: i每次自增1;
• 8. 在循环体中：
  • 将临时变量temp 记录从0~i的和的累积;
  • 判断当前的temp 是否大于 maxVaue. 如果大于MaxValue 则更新maxValue;
  • 判断当前的temp如果小于0的情况出现,则将temp 赋值为0;
• 9. 最后返回maxValue;

暴力算法代码实现

  int maxSubArray(int* nums, int numsSize){
        if(numsSize==0) return 0;
        if(numsSize==1) return nums[0];
        int i=0,temp=0,maxValue=-1024;
        for(i=0;i<numsSize;i++)
        {
            temp=temp+nums[i];
            if(temp>maxValue) maxValue=temp;
            if(temp<0) temp=0;
        }
        return maxValue;
    }

执行过程动画效果

温馨提示: 上图为动图效果 网页阅读更佳哦~

1.2.2 分治策略

站在分治策略的角度下思考, 求最大连续数组，我们可以预估到最大连续数组的和有可能出现的3个位置如下:

数组的左半部分的最大连续数组和；

数组的右半部分的最大连续数组和；

横跨数组的左半部分和右半部分得到最大连续数组和；

三者比较大小，最大者即为我们所求的最大连续数组的和。

LeetCode 执行结果

接下来，我们分析案例中提供的数组，来推演分治策略的算法思想；

如果推演过程,数组中元素太多，可能会造成大家对于分治策略中提出的 关于有可能出现最大连续数组和的3个猜想造成理解负担；

所以我们假设此时数组中只有2个元素，数组nums[2] = {-2,1}，其中-2和1只是随机设计的数字，

也就是说 这2个数字最多组成3个可能性;

-2

表示数组左半部分的有可能是最大连续数组的和;

-2 + 1

表示数组横跨左半部分和右半边部分有可能是连续数组的和;

1

表示数组右半部分有可能是最大连续数组的和;

最后， 比较这3个数字，取最大就能获得最大连续数组的和。

分治策略算法思路

分析: 分治策略在开篇我们就谈过，分治策略的本质就是将问题拆解成最小子问题，再将子问题的结合进行合并; 而连续数列问题， 其实就可以用到分治策略中的递归的方式来进行解决； 刚刚我们通过对2个元素的数列进行小基数数据的推演， 需要将数列拆解左右2个半部分， 依次递归拆解，直到只剩下一个数字时就触碰到递归的底线，那么现在我们捋顺一下这个问题的思路——

• 1. 将数列一分为二，求解mid = left + (right - left)/2 。那么为什么要这么计算mid呢，是因为数列在不断拆解的过程，数列本身就被折断了，但是我们不能记录错误的mid，mid 还是基于nums 原始数组的index ;
• 2. 递归求解数列左半部分的和 则调用 subMaxValue(nums, left, mid);
• 3. 求出左半部分和之后，则继续求解从left 跨越mid 到 right 这横跨中间部分的和MidValue(nums,left,mid,right);
• 4. 继续递归求解数列右半部分的和，则调用 subMaxValue(nums, mid+1,right);
• 5. 最后在每一次递归回调上层之前，判断left_sum,mid_sum,right_sum 谁的值更大，则返回上一层递归；
• 6. 继续递归回滚， 直到所有的递归都回滚到入口时,就求解出来连续数列的最大和。

//
//  main.c
//  001--连续数组(分治策略)
//
//  Created by CC老师 on 2020/9/7.
//  Copyright © 2020 CC老师. All rights reserved.
//

#include <stdio.h>
//宏定义无穷小
#define INF -2147483647
//求a和b的最大值
#define max( a , b ) ( a > b ? a : b )

//求跨越中点mid的最小子数组和
int MidValue( int * nums , int left , int mid , int right ){

    int left_sum = INF , right_sum = INF;
    int sum = 0;

    //求中点最半部分和
    for( int i = mid ; i >= left ; i-- ){

        sum += *( nums + i );

        if( sum > left_sum ){

            left_sum = sum;

        }

    }

    sum = 0;

    //求中点右半部分和
    for( mid++ ; mid <= right ; mid++ ){

        sum += *( nums + mid );

        if( sum > right_sum ){

            right_sum = sum;

        }

    }

    return right_sum + left_sum;

}

int subMaxValue( int * nums , int left , int right ){

    if( left >= right ){

        return *( nums + left );

    }

    int mid = left + ( right - left ) / 2;
    //仅求中点左部分和
    int left_sum = subMaxValue( nums , left , mid );
    //求跨越中点的和
    int mid_sum = MidValue( nums , left , mid , right );
    //求中点右部分和
    int right_sum = subMaxValue( nums , mid + 1 , right );
    
    return max( left_sum , max( right_sum , mid_sum ) );

}

int maxSubArray( int * nums , int numsSize ){

    return subMaxValue( nums , 0 , numsSize - 1 );

}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    //int nums[] = {-2,1,-3};
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int maxSum = maxSubArray(nums, 9);
    printf("%d\n",maxSum);
    return 0;
}

总结与分析

连续数列这个问题，我们实现了2种方法：第一种是暴力法；第二种是分治策略。但是从代码实现的结果以及他们的执行时间和内存空间占用上，可以发现第一种方法更有优势。所以在解决算法问题时，并不是单纯的认为分治策略的解决的方案就会比暴力法高级。其实算法重要的还是比较他们的时间/空间复杂度，更重要的是从不同的解决策略去实现算法， 最大的收益是开拓的解决问题的思维方式；

实际上，该问题还有一种解决方案就是动态规划，因为该篇章的主角是 "分治策略" ，所以我们就不在这篇文章中来进行喧宾夺主的事情，后续会有专门关于动态规划的篇章，我们再继续延伸学习；

算法之"高手过招" 专栏会以几大算法策略为主题的进行不断更新，后续会继续更新"分治策略"篇章。

致谢!

该文章,仅献给在编程路上, 持续热爱算法的开发者。

文章如有错误,欢迎指正~

著作权归作者所有; 未经作者授权,不得商业转载/非商业转载;

算法之"高手过招"知识付费系列下的视频/文章/源码/资料已申请版权保护！！！

END

你的每个赞和在看，我都喜欢！