剑指offer-例题连续子数组的最大和

题目描述

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

//动态规划思想 public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array==null||array.length==0) return 0; int[] sum=new int[array.length];//记录以i结尾的子数组的最大和 sum[0]=array[0]; for(int i=1;i<array.length;i++) { if(sum[i-1]<=0)//这个很重要 sum[i]=array[i]; else sum[i]=sum[i-1]+array[i]; } int max=array[0]; for(int i=1;i<array.length;i++) { if(max<sum[i]) max=sum[i]; } return max; } }