剑指offer系列之29：连续子数组的最大和-CSDN博客

本文链接：https://blog.csdn.net/ly_main/article/details/51134312

题目描述：输入一个整型数组，数组中一个或连续多个整数组成一个子数组，求所有子数组的和的最大值，要求时间复杂度为O(n)。

思路：举例分析数组的规律，这实际上是一个逐步比较的过程，假设累加进行到某一步，继续累加下一个数的时候发现和变小了，就应该重新计算当前累加的和，这实际上就是一个重新赋值的过程。如果累加之后发现变大了，这当然是我们想要的，自然就继续累加了。累加之后再判断是否大于原来的最大值，如果不是的话，就重新赋值最大值为当前累加的和（因为它更大）。其实还可以使用动态规划的思想。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        boolean invalidInput = false;
        if(array == null || array.length == 0){
            invalidInput = true;
            return 0;
        }
        invalidInput = false;
        int nCurSum = 0;
        int nGreatestSum = 0x80000000;
        for(int i = 0;i < array.length;i++){
            if(nCurSum <= 0){
                nCurSum = array[i];
            }else{
                nCurSum += array[i];
            }
            if(nCurSum > nGreatestSum){
                nGreatestSum = nCurSum;
            }
        }
        return nGreatestSum;
    }
}