package Nowcode;
/**
* HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,
* 常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
* 并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
* 你会不会被他忽悠住？(子向量的长度至少是1)
*
* @author Administrator
*
*/
public class GreatSum {
public int FindGreatestSumOfSubArray(int[] array) {
if (array == null)
return 0;
int curSum = 0;// 当前和
int maxSum = 0;// 最大子序列和
boolean flag = true;// 默认为0，如果遇到负数flag=true
for (int i = 0; i < array.length; i++) {// { 1, -2, 3, 10, -4, 7, 2, -5}
if (array[i] >= 0)
flag = false;
// 1加-2等于-1，小于0，那加上3，得到2比3还小，所以不用考虑从第一个数字开始的子数组，之前累计的和也抛弃掉
if (curSum <= 0) {
curSum = array[i];
} else {
curSum += array[i];
}
if (curSum > maxSum)
maxSum = curSum;
}
// 如果全为负数
if (flag && maxSum == 0) {
// 默认第一个为最小
int tempMax = array[0];
// 找出最小的负数
for (int i = 0; i < array.length; i++) {
if (array[i] > tempMax)
tempMax = array[i];
}
maxSum = tempMax;
}
return maxSum;
}
public static void main(String[] args) {
// int[] array = { 6, -3, -2, 7, -15, 1, 2, 2 };
int[] array = { -1, -2, -3, -10, -4, -7, -2, -5 };
// int[] array = { 1, -2, 3, 10, -4, 7, 2, -5 };
GreatSum sum = new GreatSum();
System.out.println(sum.FindGreatestSumOfSubArray(array));
}
}
