求数组中连续n个元素使其和最大

给定一个数组，求出数组中连续的一些元素使其和的值最大。如果所有元素都为正数，显然整个数组即为所求的。如果所有元素的值为负数，则所求的最大值为0.

这是在编程珠玑上看到的，其时间复杂度由O(n3)减为O(n)了。

java代码　　　

package　cn.lifx.test;　
　
public　class　MaxSum　
{　
　public　static　void　main(String[]　args)　
　{　
　int[]　arr　=　new　int[]{31,　-41,　59,　26,　-53,　58,　97,　-93,　-23,　84};　
　　
　MaxSum　ms　=　new　MaxSum();　
　　
　ms.Max(arr);　
　ms.Max2(arr);　
　ms.Max3(arr);　
　　
　int　max　=　ms.Max4(arr,　0,　arr.length-1);　
　System.out.println("Max　sum　is　"　+　max);　
　　
　ms.Max5(arr);　
　}　
　
　//方法1:　时间复杂度为O(n*n*n)　
　public　void　Max(int[]　arr)　
　{　
　int　max　=　0;　
　int　sum　=　0;　
　int　left　=　-1;　
　int　right　=　-1;　
　　
　for(int　i=0;　i<arr.length;　i++)　
　{　
　　for(int　j=i;　j<arr.length;　j++)　
　　{　
　　sum　=　0;　
　　　
　　for(int　k=i;　k<=j;　k++)　
　　{　
　　　sum　=　sum　+　arr[k];　
　　}　
　　　
　　if(sum　>　max)　
　　{　
　　　left　=　i;　
　　　right　=　j;　
　　　max　=　sum;　
　　}　
　　}　
　}　
　　
　if(right　>　0)　
　{　
　　System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);　
　}　
　else　
　{　
　　System.out.println("Max　sum　is　0　.");　
　}　
　}　
　
　//方法2：时间复杂度为O(n*n)　
　public　void　Max2(int[]　arr)　
　{　
　int　max　=　0;　
　int　sum　=　0;　
　int　left　=　-1;　
　int　right　=　-1;　
　　
　for(int　i=0;　i<arr.length;　i++)　
　{　
　　sum　=　0;　
　　for(int　j=i;　j<arr.length;　j++)　
　　{　
　　sum　=　sum　+　arr[j];　
　　if(sum　>　max)　
　　{　
　　　left　=　i;　
　　　right　=　j;　
　　　max　=　sum;　
　　}　
　　}　
　}　
　　
　if(right　>　0)　
　{　
　　System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);　
　}　
　else　
　{　
　　System.out.println("Max　sum　is　0　.");　
　}　
　}　
　
　//方法3：时间复杂度为O(n*n)　
　public　void　Max3(int[]　arr)　
　{　
　int　max　=　0;　
　int　sum　=　0;　
　int　left　=　-1;　
　int　right　=　-1;　
　　
　int[]　temp　=　new　int[arr.length+1];　
　　
　temp[0]　=　0;　
　for(int　i=0;　i<arr.length;　i++)　
　{　
　　temp[i+1]　=　temp[i]　+　arr[i];　
　}　
　　
　for(int　i=0;　i<arr.length;　i++)　
　{　
　　for(int　j=i;　j<temp.length;　j++)　
　　{　
　　sum　=　temp[j]　-　temp[i];　
　　if(sum　>　max)　
　　{　
　　　left　=　i;　
　　　right　=　j-1;　
　　　max　=　sum;　
　　}　
　　}　
　}　
　　
　if(right　>　0)　
　{　
　　System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);　
　}　
　else　
　{　
　　System.out.println("Max　sum　is　0　.");　
　}　
　}　
　
　//方法4：时间复杂度为O(n*logn)　
　public　int　Max4(int[]　arr,　int　left,　int　right)　
　{　
　int　sum　=　0;　
　int　max　=　0;　
　int　max1　=　0;　
　int　max2　=　0;　
　int　middle　=　0;　
　　
　if(left　>　right)　
　{　
　　return　0;　
　}　
　else　if(left　==　right)　
　{　
　　return　(arr[left]　>　0　?　arr[left]　:　0);　
　}　
　　
　middle　=　(left　+　right)/2;　
　　
　for(int　i=middle;　i>=left;　i--)　
　{　
　　sum　=　sum　+　arr[i];　
　　if(sum　>　max1)　
　　{　
　　max1　=　sum;　
　　}　
　}　
　　
　sum=0;　
　for(int　i=middle+1;　i<=right;　i++)　
　{　
　　sum　=　sum　+　arr[i];　
　　if(sum　>　max2)　
　　{　
　　max2　=　sum;　
　　}　
　}　
　　
　max　=　max1+max2;　
　int　temp1　=　Max4(arr,　left,　middle);　
　int　temp2　=　Max4(arr,　middle+1,　right);　
　　
　if(temp1　>　max)　
　{　
　　max　=　temp1;　
　}　
　　
　if(temp2　>　max)　
　{　
　　max　=　temp2;　
　}　
　　
　return　max;　
　}　
　
　//方法5：时间复杂度为O(n)　
　public　void　Max5(int[]　arr)　
　{　
　int　max1　=　0;　
　int　max2　=　0;　
　int　left　=　-1;　
　int　right　=　-1;　
　int　temp　=　0;　
　　
　for(int　i=0;　i<arr.length;　i++)　
　{　
　　temp　=　(max1+arr[i]);　
　　if(temp　>　0)　
　　{　
　　max1　=　temp;　
　　}　
　　else　
　　{　
　　left　=　i+1;　
　　max1　=　0;　
　　}　
　
　　if(max1　>　max2)　
　　{　
　　right　=　i;　
　　max2　=　max1;　
　　}　
　}　
　　
　if(right　>　0)　
　{　
　　System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max2);　
　}　
　else　
　{　
　　System.out.println("Max　sum　is　0　.");　
　}　
　}　
}