剑指offer No.31

No.31

题目

输入一个整型数组，数组里有正数也有负数。数组中一个或者连续的多个整数组成一个字数组。求所有字数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18

思路

因为时间复杂度为O(n)，则只能遍历一次数组，这里同时使用两个变量sum和max，其中sum保存的是当前的和，若sum<0，则从下一个位置从新记录，max记录的是历史的最大值，只有当sum>max时用sum替换max。

代码

public class Item {

    public static void main(String args[]) { 

      int array[] = {1, -2, 3, 10, -4, 7, 2, -5}; 

      System.out.println(findMax(array));

    } 

    public static int findMax(int array[]){

        //加上约束条件，防止当数组为空时造成数组越界

        if (array.length == 0) {

            return 0;

        }

        int max = array[0];

        int sum = 0;

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

            //如果加上某个元素sum>=0的话，就加；

            //当数组全为负数的时候只要有加法就一定比原来的数小,此时就相当于找出数组内最大的数

            if(sum >= 0) {

                sum += array[i]; 

            }

            else{ 

                sum = array[i]; //否则从当前位置重新计算 

            }

            if(sum > max){ 

                max = sum; 

            }

        } 

        return max; 

    }

}

---------------------

原文：https://blog.csdn.net/liuhe_5656/article/details/52474786