最大子数组

题目

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和,子数组中至少包含一个元素。http://www.lintcode.com/zh-cn/problem/maximum-subarray/

分析

首先想到了暴力搜索的方式,算出单独的,相邻两个,相邻3个,相邻n-1个的和,然后得到最大值,还可以预处理一下,把连续符号相同的元素合并,产生一个元素正负号间隔排列的新数组,同时移除首、尾的负数元素,以简化组合过程,但发现题目中有一个挑战,用O(n)完成,直接懵逼,苦思无果。

在查阅了别人的答案后,得知了最优算法,的确非常巧妙,一次遍历即可。代码很简短,思想很精妙,代码实现如下:


public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i=0; i < nums.length; i++){
            sum += nums[i];
            if(sum > max){
                max = sum;
            }
            if(sum < 0) sum = 0;
        }
        return max;
    }
}

要理解这个算法流程,还是先从最简单的情况逐步推断,枚举大法好:

  • 若数组中只包含一个元素,唯一的元素就是最大和
  • 若数组中包含2个元素,这时就要分情况讨论了。记f为取最大子数组,如果这两个元素符号均不为负,则结果为二者之和,f({a,b}) = a+b;若符号相异,则正数为最大和, 若均为负数,数值最小的元素就是最大和 f({a, b}) = max(a,b)
  • 若元素中包含了3个元素,将这三个元素分为两组,{a,b},{c},那么f({a,b})的结果就可以根据第二步得出,此时再考虑c,两者的符号一共4种情况:正正、正负、负正、负负,其结果依次为f({a,b,c}) = f({a,b}) + c , f({a, b, c}) = f({a, b}), f({a,b,c}) = c, f({a,b,c}) = max(f({a,b}, c)
  • 若元素中包含了4个元素,则此时情况又有不同。因为f({a,b,c})有可能是通过a+b,max(a,b)计算得出,在计算f({a,b,c,d})时,d并不能直接与f({a,b,c})相加,考虑{2,-3,1,4},f({2,-3, 1}) = 2。因此我们需要一个变量来存储当前最大子序列的值,同时用另一个变量来存储当前累加的元素和,一旦累加元素和超过了当前记录的最大值,就更新这个值。而一旦发现当前累加和为负,就将之清零,也就是放弃负数的子序列和。

因此,算法的具体流程为:

  • 初始化两个变量,sum为计算当前的子数列和,初始值为0,max为Integer.MIN_VALUE
  • 循环整个数组,将nums[i]叠加到sum上,若sum超过了max,则更新max的值为sum;同时,若sum<0,则这一段累加的结果可以丢弃,直接从下一个元素开始重新累加
  • 将max初始值设置为Integer.MIN_VALUE可以保证第一次进入循环时,max的值直接被nums[0]替换
Show Comments

Get the latest posts delivered right to your inbox.