HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
最开始你可以判断数组是否为空,这个代码在以下4个程序中没有体现
1 if (array == null || array.length == 0 || (array.length == 1 && array[0] <= 0)) return 0;
方法一:最好的方法 时间复杂度是O(n)
很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和
1 import java.util.*; 2 public class Solution { 3 //求连续数字之和,当和为负值,抛弃.当和为正值,比较其与最大值,如大于,则替换之 4 public int FindGreatestSumOfSubArray(int[] array) { 5 int sum = array[0]; //累加求和 6 int maxSum = array[0]; //记录最大值 7 for (int i = 1; i < array.length; i++) { 8 sum = (sum > 0) ? (sum + array[i]) : array[i]; 9 maxSum = Math.max(maxSum, sum); 10 } 11 return max; 12 } 13 }
另外初始值如果全都赋值为0的话(5行 6行为0),可以额外考虑下全为负数的情况就可以
1 public class FindMaxSumOfSubArray { 2 3 /** 4 * @param args 5 */ 6 public static void main(String[] args) { 7 FindMaxSumOfSubArray f = new FindMaxSumOfSubArray(); 8 int[] arr = { 1, -2, 3, 10, -4, 7, 2, -5 }; 9 System.out.println("MaxSum:" + f.findMaxSum(arr)); 10 } 11 12 public Integer findMaxSum(int[] arr) { 13 int curSum = 0; 14 int maxSum = 0; 15 int len = arr.length; 16 17 if (arr == null || len == 0) { 18 return null; 19 } 20 21 for (int i = 0; i < len; i++) { 22 curSum += arr[i]; 23 if (curSum < 0) { 24 curSum = 0; 25 } 26 if (curSum > maxSum) { 27 maxSum = curSum; 28 } 29 } 30 31 // all data are negative 32 if (maxSum == 0) { 33 for (int i = 0; i < len; i++) { 34 if (i == 0) { 35 maxSum = arr[i]; 36 } 37 if (arr[i] > maxSum) { 38 maxSum = arr[i]; 39 } 40 } 41 } 42 return maxSum; 43 } 44 }
方法二 暴力求解法
时间复杂度是O(n3)
空间复杂度是O(1)
1 import java.util.*; 2 public class Solution { 3 public int FindGreatestSumOfSubArray(int[] array) { 4 int len = array.length; 5 int maxSum =java.lang.Integer.MIN_VALUE;//起初赋值为0,则输入样例全是负数的情况下,代码不通过 6 for(int i=0;i<len;i++){//每一个可能开始的点 7 for(int j=i;j<len;j++){//每个可能结束的点 8 int temp =0; 9 for(int k=i;k<=j;k++) temp+=array[k];//从可能的起始点到可能的终点,求和 10 if(temp>maxSum) maxSum = temp; 11 } 12 } 13 return maxSum; 14 } 15 }
方法三 在上面个的第9行代码中, 如果求得 i ..... j-1;再进行一次加法,就可以得到i.....j的和,不用再重新加一遍
时间复杂度是O(n2) 少了一个量级
空间复杂度是O(1)
1 import java.util.*; 2 public class Solution { 3 public int FindGreatestSumOfSubArray(int[] array) { 4 int len = array.length; 5 int maxSum =java.lang.Integer.MIN_VALUE;//起初赋值为0,则输入样例全是负数的情况下,代码不通过 6 for(int i=0;i<len;i++){//每一个可能开始的点 7 int temp =0; //为了改进上一方法的第9行代码,需要提前赋值 8 for(int j=i;j<len;j++){//每个可能结束的点 9 temp+=array[j]; 10 if(temp>maxSum) maxSum = temp; 11 } 12 } 13 return maxSum; 14 } 15 }
原文：https://www.cnblogs.com/shareidea94/p/11096723.html
