问题描述

给定整数 ，求的最大值。约定当所有整数都为负数时，最大子序列的和为0。

解决思路分析

思路一

将整个序列的所有子序列遍历一遍，求这些所有子序列中的最大值。 java代码如下：

	  public static int maxSubSum1(int data[]) {
	    int maxSum = 0;
	    for (int i = 0; i < data.length; i++)
	      for (int j = i; j < data.length; j++) {
	        int tempSum = 0;
	        for (int k = i; k <= j; k++) {
	          tempSum += data[k];
	        }
	        if (tempSum > maxSum) {
	          maxSum = tempSum;
	        }
	      }
	    return maxSum;
	  }

时间复杂度：O(n^3)</br> 空间复杂度：O(1)

思路二

对思路一尽行优化，即在遍历所有子序列时向后遍历，即可省去第3层循环 java代码如下：

	  public static int maxSubSum2(int data[]) {
	    int maxSum = 0;
	    for (int i = 0; i < data.length; i++) {
	      int tempSum = 0;
	      for (int j = i; j < data.length; j++) {
	        tempSum += data[j];
	        if (tempSum > maxSum) {
	          maxSum = tempSum;
	        }
	      }
	    }
	    return maxSum;
	  }

时间复杂度：O(n^2)</br> 空间复杂度：O(1)

思路三

使用二分分治的思想，即将整个序列分为前后两部分，那么该最大子序列可能出现在前半部分，也可能出现在后半部分，也有可能同时包含了两个部分（此情况下必定包含前半部分的最后一个元素，也必定包含后半部分的第一个元素），按照此思路我们可以设计一个递归函数，一直二分下去，在上述3种情况下求最大值即为最大子序列和。</br>

java代码如下：

	  private static int maxSumRec(int[] data, int head, int end) {
	    if (head == end) {
	      if (data[head] > 0) {
	        return data[head];
	      } else {
	        return 0;
	      }
	    }
	
	    int middle = (head + end) / 2;
	    int maxHeadSum = maxSumRec(data, head, middle);
	    int maxEndSum = maxSumRec(data, middle + 1, end);
	
	    int maxHeadBorderSum = 0;
	    int tempHeadBorderSum = 0;
	    for (int i = middle; i >= head; i--) {
	      tempHeadBorderSum += data[i];
	      if (tempHeadBorderSum > maxHeadBorderSum) {
	        maxHeadBorderSum = tempHeadBorderSum;
	      }
	    }
	
	    int maxEndBorderSum = 0;
	    int tempEndBorderSum = 0;
	    for (int i = middle + 1; i <= end; i++) {
	      tempEndBorderSum += data[i];
	      if (tempEndBorderSum > maxEndBorderSum) {
	        maxEndBorderSum = tempEndBorderSum;
	      }
	    }
	
	    int maxBorderSum = maxHeadBorderSum + maxEndBorderSum;
	    int temp = 0;
	    return (temp = (maxEndSum > maxHeadSum ? maxEndSum : maxHeadSum)) > maxBorderSum ? temp
	        : maxBorderSum;
	  }

	  public static int maxSubSum3(int data[]) {
    	return maxSumRec(data, 0, data.length - 1);
  	  }

时间复杂度：O(nlogn)</br> 空间复杂度：O(1)

思路四

最为精巧的算法实现，即当一个从头开始遍历的子序列和为负数时，忽略掉这个子序列中的所有元素，再从剩下的元素中去求最大序列和。 java代码如下：

	  public static int maxSubSum4(int data[]) {
	    int maxSum = 0;
	    int tempSum = 0;
	
	    for (int i = 0; i < data.length; i++) {
	      tempSum += data[i];
	      if (tempSum < 0) {
	        tempSum = 0;
	      }
	      if (tempSum > maxSum) {
	        maxSum = tempSum;
	      }
	    }
	
	    return maxSum;
	  }

时间复杂度：O(n)</br> 空间复杂度：O(1)

结论

在这四个实现中，我们发现了一个问题，即实现起来简单易懂的算法往往效果并不太好，而那些所谓精妙的算法，虽然相对难以理解一些，但往往可以取得非常好的效果。此外，当我们一时想不到这些精妙的算法时，折衷的做法是利用分治的思想，因为这个思想是“万金油”，到哪儿都能较好的解决问题，相对也容易理解一些。