求带有非负数的数组中随意连续子项相加的最大值——算法最优解

直接上代码，这是在慕课大学上学的，算是笔记吧~~~

public class TestArith {    
   public  static void main(String[] args){       
     int array[]={-1,3,-2,4,-6,1,6,-1};     
     int sum=0;   
     int maxSum=0;        
    for (int i = 0; i < array.length; i++) {          
      sum +=array[i];//向右累加         
       if (sum>maxSum){              
        maxSum=sum;//发现更大和则更新当前结果            
    }else if (sum<0){              
        sum=0;//如果当前子列和为负，则不可能使后面的部分和增大，抛弃之                
    }      
  }        
System.out.print(maxSum);  
  }
}

算法的复杂度为O(N),即遍历一遍即可算出答案。原图如下：

Paste_Image.png