/**
* 输入一个整型数组，数组里有正数也有负数。
* 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
* 求所有子数组的和的最大值。要求时间复杂度为O(n)。
* 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
* 因此输出为该子数组的和18。
* 最简单的办法就是穷尽所有的子数组，计算他们的和，然后比较
*
int maxSum(int arr[]){
int maximum = arr[0];
int sum=0;
for(int i = 0; i < arr.length; i++){
for(int j = i; j < arr.length; j++) {
for(int k = i; k <= j; k++) {
sum += A[k];
}
if(sum > maximum)
maximum = sum; sum=0;
}
}
return maximum;
} */
public class MaxSum {
/** * *依次遍历数组中的元素，把它们相加，如果加起来b
* <0， *把b重新赋值，置为下一个元素，b=a[i]。
* *当b>sum，则更新sum=b; *若b<sum，则sum保持原值，不更新 */
public static int maxSum(int arr[]){
int sum = arr[0];
int b = 0;
for(int i = 0;i<arr.length;i++){
if(b<=0)
b=arr[i];
else
b+=arr[i];
if(b>sum)sum=b;
}
return sum;
}
public static void main(String[] args) {
//int arr[]={1,-2,3,10,-4,7,2,-5};
int arr[]={-1,-2,-3,-10,-4,-7,-2,-5};
int result = maxSum(arr);
System.out.println(result);
}
}
