算法的思路

先说一个简单地题目,有一个无序的list里面存放了很多整数(有正有负),
如何去求出它的最小子序列和呢?(最小子序指的是连续的子list之和最小,如果都是正数则为0)

比如说有一个list = [1,-3,-2,5,2,-6],那么这个list的最小子序和则是-6,如果
list = [1,-3,-2,5,2,-4],那么这个list的最小子序和则是-5.

最简单的穷举法

这个问题初看很简单,就是两个循环记录每个子序的和,然后找出最小的和。很容易写出这样的算法:

int subMin(int *list, int length){

    int minSum = 0;
    for (int i=0; i < length; i++) {
        for (int j=i; j < length; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += *(list+k);
            }

            if (sum < minSum) {
                minSum = sum;
            }
        }
    }

    return minSum;
}

这个算法非常简单,思路也很清晰,既然需要求最小的那个子序,那我就列出每一个子序求和,得出最小的那个。第一个循环用来标记起始位,第二个循环标记结束位,最里面一层循环用来计算起始位到结束位的和。

进击的穷举法

这个算法虽然写起来很简单,但显而易见的时间复杂度非常高。这种思路下的算法只能作为备用,这种算法也有一个种称号叫穷举法。那么我们来看下这个算法是否还有改进的地方:

int subMinUpgrade(int *list, int length){

    int minSum = 0;
    for (int i=0; i < length; i++) {

        int sum = 0;
        for (int j=i; j < length; j++) {

            sum += *(list + j);

            if (sum < minSum) {
                minSum = sum;
            }
        }
    }

    return minSum;
}

经过分析,其实能发现,第三层的循环是多余的,因为在第二层循环的时候已经能够穷举每一种情况了,只是不够直观,这个思路利用了在建立穷举界限的步骤中加入运算的步骤来简化。很明显时间复杂度下降了一个量级。但是这就是一个我们所追求的好的算法么!

分治的思路

归根到底,这种算法也还是一种穷举法,会遍历所有的情况,既然这样,那我能不能每次循环中做的事情更多一点,或者能不能减少循环的次数呢?带着这样的想法,我尝试了把这个队列一分为二,这样我就能减少循环次数了,但是分成两份后怎样去求最小的子序和呢?

举个例子:30,-25,14,-24,1,35,-25,10,这个list。想要求出最小值我们其实可以求左边4个的最小值,或者右边4个的最小值,然后求出横跨两边的最小值,最后求出这三者的最小值,那就是我们需要的最小值。

int subMinRecursion(int *list, int start, int end){
    int minSumLeft = 0;
    int minSumRight = 0;

    int sumLeftCross = 0;
    int minSumLeftCross = 0;

    int sumRightCross = 0;
    int minSumRightCross = 0;

    if (start == end) {
        if (*(list+start) > 0) {
            return 0;
        }else{
            return *(list+start);
        }
    }else{

        int mid = (end + start)/2;


        minSumLeft = subMinRecursion(list, start, mid);
        minSumRight = subMinRecursion(list, mid+1, end);

        for (int i = end/2; i >= start; i--) {
            sumLeftCross += *(list+i);

            if (sumLeftCross < minSumLeftCross) {
                minSumLeftCross = sumLeftCross;
            }
        }

        for (int i = end/2 + 1; i <= end; i++) {
            sumRightCross += *(list+i);

            if (sumRightCross < minSumRightCross) {
                minSumRightCross = sumRightCross;
            }
        }

        return minOfThree(minSumLeft, minSumRight, minSumLeftCross + minSumRightCross);

    }
}

很长但是也很好理解,每次的在最小值的计算都是基于子list的最小值,如果是正数就返回0表示排除。总的来说时间复杂度在NlogN级别。

那么为什么这个算法可以降低时间复杂度呢,原因就在于他用到了分治的思路,每一次循环都能减少前一次一半的情况,这样的思路我们可以运用到很多场景,比如说二分查找,二分排序等,包括二叉树建立的思路也是这样的。

换个角度

这里先给出程序,让我们来看下这样的问题还能玩出什么花样?

int subMinOther(int* list, int length){
    int sumSubMin = 0;
    int minSumSubMin = 0;

    for (int i=0; i < length; i++) {
        sumSubMin += *(list+i);

        if (sumSubMin < minSumSubMin) {
            minSumSubMin = sumSubMin;
        }else if(sumSubMin > 0){
            sumSubMin = 0;
        }
    }

    return minSumSubMin;
}

这里主要就用到了一个技巧,就是如果连续的累加值超过0了那可以把前面的累加值看成0,而只需要用另外一个变量记录下来之前的最小值,然后反复不断的查找一段一段的最小值,直到最后找出真实最小的那一个值。

总结

那么这样的一个例子说明了什么呢?总的来说,碰到任何问题,穷举总是能解决问题的,但是在有限的资源下,如何更好地利用就是我们需要思考的问题,很多人要问就算我知道了这样的解法有什么用呢?不说别的单单指这一个例子就能运用到很多地方。

比如说,以前玩游戏经常买卖装备赚差价,有时候高有时候低,如果做一个统计以后,最后就能得出大致在什么时间点是能够卖得最高的,那今后就能够利用这个点去赚钱,再比如说,每个公司都有自己的数据统计,如何从海量的数据中找出那个最有价值的数据。

最后再附上一道题目一起来思考下如何用有限的资源完成无限的可能:
假设有一个文件,包含了1000万条数据,每条数据都是一个7位整数,并且没有重复(e.g 00000000-9999999),在最多只有1M内存空间可用的情况下,如何进行排序呢?当然运行时间越少越好。