[分享]求拥有子串的最大和,算法复杂度O(n)

求拥子串的最大和,算法复杂度O(n)

public class Test {

	 public static int max(int[] src) {
	  int sum = src[0];
	  int minsum = src[0];
	  int maxsum = src[0];
	  int sum1 = src[0];
	  int sum2 = src[0];
	  int max = src[0];
	  
	  for (int i = 1; i < src.length; i++) {
	   sum += src[i];

	   if (sum1 > 0) {
	    sum1 += src[i];
	   } else {
	    sum1 = src[i];
	   }

	   if (sum2 < 0) {
	    sum2 += src[i];
	   } else {
	    sum2 = src[i];
	   }

	   if (sum1 > maxsum) {
	    maxsum = sum1;
	   }

	   if (sum2 < minsum) {
	    minsum = sum2;
	   }
	  }
	  max = maxsum > sum - minsum ? maxsum : sum - minsum;
	  
	  if(minsum == sum) {
	   max = maxsum;
	  }
	  
	  return max;
	 }
	 
	 public static void main(String[] args) {
	  int src[] = { 8,11, 2, 3,-6,  6, 7, 8 };
	  System.out.println(Test.max(src));
	 }

	}