java 求连续子数组的最大和

题目：

输入一个整型数组，里面有正数也有负数，数组中一个或连续多个整数组成一个子数组，求所有子数组和的最大值。要求时间复杂度为O(n)

解题思路：

从头到尾遍历整个数组，用一个整数记录子数组和的最大值，如果子数组和大于这个值，则更新最大值，如果子数组和为负，子数组和清零，然后继续往后遍历。考虑数组全是负数、数组为空等边界情况即可。

算法如下：

public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array==null||array.length==0){
return 0;
        }
int sum = 0;
int maxSum = 0;
int maxNumber = Integer.MIN_VALUE;
for(int i=0;i<array.length;i++){
if(array[i]>maxNumber){
                maxNumber = array[i];
            }
        }
if(maxNumber<0){
return maxNumber;
        }
for(int i=0;i<array.length;i++){
sum = sum+array[i];
if(sum>maxSum){
                maxSum = sum;
            }
if(sum<0){
sum = 0;
            }
        }
return maxSum;
    }
}