第二周总结

本周进行课程介绍,完成代码--返回一个整数数组中最大子数组的和（一）

package yiweishuzu;

import java.util.Scanner;

/**
* 贪心算法
* @author Lenovo
*
*/
public class shuzu_3 {
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);
}
}

基本思路就是：先求出字符串中所有元素的和，然后再求出最小字串的值，就可以求出最大的字串的和了。

　　因为在输入的字符串中，既有正数又有负数，所以在计算的过程中，所求的的最小的字串的和，就一定是包含负数最多的字串，将这些包含最多的负数的字串减去，那么剩下的就一是包含正数最多的字串，在验证的过程中，就算是子串数全部都是正数，那也一定是比计算出来的值要小，所以，在一维数组中，就一定是这样计算了。

截图：

总结:任务不是很复杂，但是说实话，要做到时间复杂度为O（n）还是很不好想的，所以说，还是编程少。