《剑指offer》练习-面试题42-连续子数组的最大和

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

思路：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对于整体和是有贡献的。如果前几项累计值为负数，则认为有害于总和。用total来记录当前累计值，maxSum记录最大和。

package offer;

import java.util.Scanner;

public class Solution41 {

	/*
	 * 算法时间复杂度O（n） 用total记录累计值，maxSum记录和最大
	 * 基于思想：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对
	 *           整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。 此时 若和大于maxSum 则用maxSum记录下来
	 */
	public int FindeGreatestSumOfSubArray(int[] array) {
		if (array.length == 0)
			return 0;
		else {
			int total = array[0], maxSum = array[0];
			for (int i = 1; i < array.length; i++) {
				if (total >= 0)
					total += array[i];
				else
					total = array[i];
				if (total > maxSum)
					maxSum = total;
			}
			return maxSum;
		}
	}

	public static void main(String[] args) {
		Solution41 sl = new Solution41();
		Scanner scanner = new Scanner(System.in);
		System.out.print("请输入数组长度length=");
		int length = scanner.nextInt();
		int[] array = new int[length];
		System.out.print("请输入一个数组：");
		for (int i = 0; i < length; i++) {
			array[i] = scanner.nextInt();
		}
		scanner.close();
		System.out.println("最大和为：" + sl.FindeGreatestSumOfSubArray(array));

	}
}

链接：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
来源：牛客网