题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
这里采用一种时间复杂度为 O(n)，空间复杂度为 O(1) 的解法。
具体思路为：首先定义一个 int型的变量 maxSum，初始值为0，用于保存连续子数组的最大和即最终结果，再定义一个 int型的变量 temp，初始值为0，用于保存当前所遍历到的子数组的和。然后对整个数组进行遍历，对于遍历到的每一个元素，都尝试性地将其累加到 temp上去，① 如果得到的 temp 小于0，说明当前元素是个负数且对于最终结果没有任何贡献，则将 temp 重置为 0，并继续扫描下一个元素；② 如果得到的 temp 不小于 0，则 temp 的值修改为累加后的值。每次处理完一个元素之后，都应当对 maxSum 进行更新，即把temp 和 maxSum 中的较大值赋给 maxSum，这样做的目的是保存截止当前为止的最大值。
注意，对整个数组遍历完之后，如果 maxSum 的值为 0 ，那么说明整个数组当中的元素都是负数，那么这个时候只需要对数组再进行一次遍历，找出其中的最大值，该最大值便是连续子数组的最大和。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int temp = 0;
int maxSum = 0;
for (int i = 0;i < array.length;i++) {
if (temp + array[i] < 0) {
temp = 0;
} else {
temp = temp + array[i];
}
maxSum = max(temp,maxSum);
}
if (maxSum == 0) {
maxSum = array[0];
for (int number : array) {
if (number > maxSum) {
maxSum = number;
}
}
}
return maxSum;
}
private int max(int a,int b) {
return a > b ? a : b;
}
}
