[算法]滴滴笔试题——求最大子串和（O(n)复杂度）

扫描法。一次扫描数组即可得出答案，复杂度O(n)。这种方法用文字描述不容易说清楚，下面用每一步运算的图示来表达。伪代码如下：

 maxsofar=end=;

 for i=[,n)

     end=max(end+x[i],)

     maxsofar=max(maxsofar,end)

即使后面没有这样的值了，maxsofar中还保存了原来的最大和，有恃无恐。这里的一条重要原则是目前end的值必须>0，如果<0，则不用考虑，立刻放弃end目前的值，将它置为0，并且把end的指针指向58。

以此类推下去，最后可得正确的结果。

整理之后的代码：

public int maxSubArray(int[] nums) {

        // write your code here

        int sum = Integer.MIN_VALUE;

        int maxsofar = Integer.MIN_VALUE;

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

            if(sum > 0){

                sum += nums[i];

            }else{

                sum = nums[i];

            }

            if(maxsofar < sum){

                maxsofar = sum;

            }

        }

        return maxsofar;

    }

参考：http://blog.nlogn.cn/programming-pearls-the-maximum-sum-of-substring/

http://www.cnblogs.com/yuwenfeng/p/4121451.html

巴特西

[算法]滴滴笔试题——求最大子串和（O(n)复杂度）

最新文章

热门文章