53、最大字序和——LeetCode

题目表述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

最大子序和

解法

暴力解法

思路

最容易想到的肯定是暴力解法,也就是一个一个逐一遍历。先把长度为一的连续子数组遍历一遍,再依次遍历到长度为numsSize的连续数组,找到和最大的那个连续数组的和即可。

这样来看,就需要先有一个长度遍历循环,再嵌套一个开始位置循环,再嵌套一个逐个累加循环。这样看来,时间复杂度是着实不小。虽然结果是对的,但是也超过了最大执行时间,没有通过测试。代码如下:

代码

int maxSubArray(int* nums, int numsSize){
    //如果为空,则直接返回0
    if (!numsSize)
        return 0;
    int max = nums[0];
    //长度循环
    for (int i = 1; i <= numsSize; ++i) {
        //累加开始的位置遍历
        for (int j = 0; j < numsSize+1-i; ++j) {
            //和
            int sum = 0;
            //遍历计算和
            for (int k = j; k < j+i; ++k) {
                sum += nums[k];
            }
            //保持max为最大的和
            max = max > sum? max:sum;
        }
    }
    return max;
}

效率实在是太低了,但也是最容易想到的。

后面的贪心法和动态分析法就是一种线性算法,时间复杂度为O(n)。

贪心法和动态分析法

思路

所谓贪心法,就是在计算最大字序和的时候,此时的字序和等于它之前的字序和加上当前数的总和。也就是说,要计算下一个位置的字序和,就将当前的数值加上之前的字序和。到这里我们就会困惑,这样怎么能线性的求出最大的字序和呢?

我们在计算当前位置的字序和的时候,如果加上当前的数值之后的和小于之前的数值大小,那就证明之前的字序和为负,对于当前的字序和造成了负增长,那么我们就舍弃掉之前的字序和,将字序和设置为当前这个数字的数值大小。之后判断此时的字序和是否大于最大字序和,如果大于,则将更新一下最大字序和的数值即可。

代码如下

int maxSubArray(int* nums, int numsSize){
    //如果为空,则返回0
    if (!numsSize)
        return 0;
    int max, sum;
    //将最大字序和、一串字序的和设置为第一个元素的值
    max = sum = nums[0];
    //遍历循环整个数组,线性遍历
    for (int i = 1; i < numsSize; i++){
        //如果sum加上当前元素的值还小于这个元素原来的值,则证明sum为负,舍弃之,将sum设置为此时元素的值
        //也可以说,当sum小于0的时候舍弃原来的sum,一样的道理
        sum = (sum+nums[i])>nums[i]? (sum+nums[i]):nums[i];
        //如果sum大于max,则将max设置为sum
        //即更新一个max的值,使之一直保持最大
        max = max>sum? max:sum;
    }
    return max;
}

此时,执行效率不知提升了多少倍,执行时间仅为8ms。这个算法的关键就是贪心法或者动态分析法的思路。

就是看前一个sum是否会对当前的字序和造成负增长,如果是则舍弃。

总结

遇到一个题目的时候,我门总是想以最简单、最无脑的方法解决。这样想也无可厚非,但是在这之后,我们还是要看看有什么更好的,更高效的方法。唯有这样,我们才能不断的进步。

另外,贪心法和动态分析法是一个很重要的算法思想,它们在许许多多的地方都有很普遍的应用。我们应该掌握这些思想。