package ketang01;
import java.util.Scanner;
/**
* 贪心算法
* @author Lenovo
*
*/
public class c1 {
private static Scanner scan;
public static void main(String[] args) {
// 确定元素的个数
System.out.println("输入数组元素个数：");
scan = new Scanner(System.in);
int n = scan.nextInt();
// 循环输入数组元素
System.out.println("输入数组");
int[] x = new int[n];
for (int i = 0; i < n; i++) {
x[i] = scan.nextInt();
}
// 最大子数组的起始位置（即当前最大子数组）
int max = Integer.MIN_VALUE;// 设置成最小整数
int sum = 0;// 记录数组个元素相加的和
for (int i = 0; i < n; i++) {// 将个元素依次相加并进行判断
if (sum <= 0) {// 当遇到小于0的数时就停止相加
sum = x[i];
} else {
sum = sum + x[i];
}
if (sum > max) {// 如果求得总和大于之前的最大值的话，就将sum赋值给max
max = sum;
}
// if (sum < 0) {// 如果当前求得的数组的和为负数，就把他清除为0(输出的结果就是非负整数)
// max = 0;
// }
}
System.out.println("最大子数组的和为：" + max);
}
}